Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Finding Minimum Congestion Spanning Trees

João Carlos Setubal, Arlindo F. Conceição, and Renato F. Werneck


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.


Publication typeInproceedings
Published inProceedings of the Third Workshop on Algorithm Engineering (WAE'99)
SeriesLecture Notes in Computer Science
PublisherSpringer Verlag
> Publications > Finding Minimum Congestion Spanning Trees