ON THE PROBLEM OF PACKING STEINER TREES OF A GRAPH

In this talk, we are concerned with undirected graphs G = (V, E), with distinguished set of vertices K  V, K 2 called the terminal vertices. A K-Steiner tree T of G is a minimal tree, containing all the vertices of K, and any vertex of degree 1 in T must belong to K. The K-edge connectivity, denoted as K(G), of a connected graph G with terminal vertices , is the minimum number of edges whose removal disconnects at least two vertices of K. The degree of a vertex v of G is the number of edges incident at v in G. In this talk, we will investigate the relationship between the maximum number of edge-disjoint K-Steiner trees, tK (G), and the K-edge-connectivity of a graph G. This problem known as the “Steiner tree packing problem” (STPP for short) has attracted considerable attention from researchers in different areas because of its wide applicability. It has applications in routing problems arising in VLSI circuit design, where an effective way of sharing different signals amongst cells in a circuit can be achieved by the use of edge-disjoint Steiner trees. In this talk we are interested in finding a lower bound of the number of edge-disjoint K-Steiner trees, tK(G) with respect to the K-edge-connectivity, K(G), and in particular we present the most recent results pertaining this problem.