摘要: The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs a given graph G that connect set required points S. This motivated by practical applications in VLSI- layout and broadcasting, as well theoretical reasons. In this paper, we study present an algorithm with asymptotic approximation factor vSv/4. gives sufficient condition for existence k trees terms edge-connectivity graph. We will show best possible if terminals 3. At end, consider fractional version problem, observe it can be reduced minimum tree via ellipsoid algorithm.
acm.org
ualberta.ca 
lens.org 参考文章(15)
L. Petingi, Bounds on the Maximum Number of Edge-disjoint Steiner Trees of a Graph ,(2000)
Karl Menger, Zur allgemeinen Kurventheorie Fundamenta Mathematicae. ,vol. 10, pp. 96- 115 ,(1927) , 10.4064/FM-10-1-96-115
D. Wagner, Simple algorithms for Steiner trees and paths packing problems in planar graphs CWI quarterly. ,vol. 6, pp. 219- 240 ,(1993)
A. Martin, R. Weismantel, Packing paths and Steiner trees: routing of electronic circuits CWI quarterly. ,vol. 6, pp. 185- 204 ,(1993)
J. Duane Northcutt, James G. Hanko, Alan T. Ruberg, Gerard A. Wall, Method and apparatus for adaptably providing data to a network environment ,(1999)
JØrgen Bang-Jensen, András Frank, Bill Jackson, Preserving and Increasing Local Edge-Connectivity in Mixed Graphs SIAM Journal on Discrete Mathematics. ,vol. 8, pp. 155- 178 ,(1995) , 10.1137/S0036142993226983
Kamal Jain, Mohammad Mahdian, Amin Saberi, A new greedy approach for facility location problems symposium on the theory of computing. pp. 731- 740 ,(2002) , 10.1145/509907.510012
C. St.J. A. Nash-Williams, Edge-Disjoint Spanning Trees of Finite Graphs Journal of the London Mathematical Society. ,vol. s1-36, pp. 445- 450 ,(1961) , 10.1112/JLMS/S1-36.1.445
M. Grötschel, A. Martin, R. Weismantel, The Steiner tree packing problem in VLSI design Mathematical Programming. ,vol. 78, pp. 265- 281 ,(1997) , 10.1007/BF02614374
András Frank, Tamás Király, Matthias Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs Discrete Applied Mathematics. ,vol. 131, pp. 373- 383 ,(2003) , 10.1016/S0166-218X(02)00463-8