Abstract
Given an undirected multigraph G and a set \(\mathcal{S}:=\{S_{1},...,S_{t}\}\) of disjoint subsets of vertices of G, a Steiner \(\mathcal{S}\)-forest F is an acyclic subgraph of G such that each S i is connected in F for 1 ≤ i ≤ t. In this paper, we study the Steiner Forest Packing problem where we seek a largest collection of edge-disjoint \(\mathcal{S}\)-forests. The main result is a connectivity-type sufficient condition for the existence of k edge-disjoint \(\mathcal{S}\)-forest, that yields the first polynomial time approximation algorithm for the Steiner Forest Packing problem. We end this paper by a conjecture in a more general setting.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Packing Problem
- Extension Property
- Extension Theorem
- Common Path
- Polynomial Time Approximation Algorithm
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chekuri, C., Shepherd, B.: Approximate integer decompositions for undirected network design problems (2004) (Manuscript)
Cheriyan, J., Salavatipour, M.: Hardness and approximation results for packing Steiner trees problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 180–191. Springer, Heidelberg (2004)
Fránk, A., Király, T., Kriesell, M.: On decomposing a hypergraph into k connected sub-hypergraphs. Discrete Applied Mathematics 131, 373–383 (2003)
Goemans, M., Williamson, D.: A general approximation technique for constrained forests problems. SIAM Journal on Computing 24, 296–317 (1995)
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39–60 (2001)
Jain, K., Mahdian, M., Salavatipour, M.R.: Packing Steiner trees. In: Proceedings of the 14th Annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 266–274 (2003)
Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph. J. Combin. Theory, Series B 88, 53–63 (2003)
Kriesell, M.: Disjoint Steiner trees in graphs without large bridges (2004) (manuscript)
Lau, L.C.: An approximate max-Steiner-tree-packing min-Steiner-cut theorem. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 61–70 (2004)
Mader, W.: A reduction method for edge-connectivity in graphs. Ann. Discrete Math. 3, 145–164 (1978)
Menger, K.: Zur allgemeinen Kurventheorie. Fund. Math. 10, 95–115 (1927)
Nash-Williams, C.S.J.A.: Edge disjoint spanning trees of finite graphs. J. London Math. Soc. 36, 445–450 (1961)
Petingi, L., Rodriguez, J.: Bounds on the maximum number of edge-disjoint Steiner trees of a graph. Congressus Numerantium 145, 43–52 (2000)
Tutte, W.T.: On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36, 221–230 (1961)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lau, L.C. (2005). Packing Steiner Forests. In: Jünger, M., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2005. Lecture Notes in Computer Science, vol 3509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496915_27
Download citation
DOI: https://doi.org/10.1007/11496915_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26199-5
Online ISBN: 978-3-540-32102-6
eBook Packages: Computer ScienceComputer Science (R0)