Abstract
Given a graph G and a positive integer k, we want to find k spanning trees on G, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty function if it belongs to more than one tree. We present a polynomial time algorithm for this problem; the algorithm’s complexity is quadratic in k. We also present two heuristics with complexity linear in k. In an experimental study we show that these heuristics are much faster than the exact algorithm also in practice, and that their solutions are around 1% of optimal for small values of k and much better for large k.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Ahuja, T. Magnanti, and J. Orlin. Network flows. Prentice-Hall, 1993.
T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press/McGraw Hill, 1990.
J. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards, 65B:67–72, 1965.
J. Edmonds. Lehman’s switching game and a theorem of Nash-Williams. J. Res. Nat. Bur. Standards, 65B:73–77, 1965.
C. St. J. A. Nash-Williams. Edge-disjoint trees of finite graphs. J. London Math. Soc., 36:445–450, 1961.
J. Roskind and R. Tarjan. A note on finding minimum-cost edge-disjoint spanning trees. Mathematics of Operations Research, 10(4):701–708, 1985.
W. Tutte. 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
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Werneck, R.F.F., Setubal, J.C., da Conceição, A.F. (1999). Finding Minimum Congestion Spanning Trees. In: Vitter, J.S., Zaroliagis, C.D. (eds) Algorithm Engineering. WAE 1999. Lecture Notes in Computer Science, vol 1668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48318-7_7
Download citation
DOI: https://doi.org/10.1007/3-540-48318-7_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66427-7
Online ISBN: 978-3-540-48318-2
eBook Packages: Springer Book Archive