NOTE ON FINDING MINIMUM-COST EDGE-DISJOINT SPANNING TREES.

James Roskind, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

99 Scopus citations

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 languageEnglish (US)
Pages (from-to)701-708
Number of pages8
JournalMathematics of Operations Research
Volume10
Issue number4
DOIs
StatePublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'NOTE ON FINDING MINIMUM-COST EDGE-DISJOINT SPANNING TREES.'. Together they form a unique fingerprint.

Cite this