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 plus k**2n**2) time. If all edge costs are the same, the algorithm runs in O(k**2n**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.
Original language | English (US) |
---|---|
Pages (from-to) | 701-708 |
Number of pages | 8 |
Journal | Mathematics of Operations Research |
Volume | 10 |
Issue number | 4 |
DOIs | |
State | Published - 1985 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics
- Computer Science Applications
- Management Science and Operations Research