A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
James Roskind, Robert E. Tarjan
Source abstract
Let G be an undirected graph with n vertices and m edges, such that each edge has a real-valued cost. We consider the problem of finding a set of k edge-disjoint spanning trees in G of minimum total edge cost. This problem can be solved in polynomial time by the matroid greedy algorithm. We present an implementation of this algorithm that runs in O(m log m + k 2 n 2 ) time. If all edge costs are the same, the algorithm runs in O(k 2 n 2 ) time. The algorithm can also be extended to find the largest k such that k edge-disjoint spanning trees exist in O(m 2 ) time. We mention several applications of the algorithm.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.