Finding Minimum Congestion Spanning Trees

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

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.

Details

Publication typeInproceedings
Published inProceedings of the Third Workshop on Algorithm Engineering (WAE'99)
URLhttp://www.springerlink.com/content/x7j6aup7rvlqk46p/?MUD=MP
Pages60-71
Volume1668
SeriesLecture Notes in Computer Science
PublisherSpringer Verlag
> Publications > Finding Minimum Congestion Spanning Trees