Premium
Packing the Steiner trees of a graph
Author(s) -
Petingi L.,
Talafha M.
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20298
Subject(s) - combinatorics , steiner tree problem , mathematics , vertex (graph theory) , conjecture , graph , disjoint sets , undirected graph , connectivity , neighbourhood (mathematics) , spanning tree , discrete mathematics , mathematical analysis
Let G = ( V , E ) be an undirected graph with a distinguished set of terminal vertices K ⊆ V , | K | ≥ 2. A K ‐Steiner tree T of G is a tree containing the terminal vertex‐set K , where any vertex of degree one in T must belong to K . The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge‐disjoint K ‐Steiner trees, t K ( G ), contained in G . Specifically we are interested in finding a lower bound on t K ( G ) with respect to the K ‐edge‐connectivity, denoted as λ K ( G ). In 2003, Kriesell conjectured that any graph G with terminal vertex‐set K has at least ⌊λ K ( G )/2⌋ edge‐disjoint K ‐Steiner trees. In this article, we show that this conjecture can be answered affirmatively if the edges of G can be partitioned into K ‐Steiner trees. This result yields bounds for the problem of packing K ‐Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex‐set K , t K ( G ) ≥ ⌊λ K ( G )/2⌋ − | V − K |/2 − 1. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009