Finding Minimum Congestion Spanning Trees

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

1999

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.

In Proceedings of the Third Workshop on Algorithm Engineering (WAE'99)

Publisher Springer Verlag

Type | Inproceedings |

URL | http://www.springerlink.com/content/x7j6aup7rvlqk46p/?MUD=MP |

Pages | 60-71 |

Volume | 1668 |

Series | Lecture Notes in Computer Science |

> Publications > Finding Minimum Congestion Spanning Trees