Minimum-cost spanning tree as a path-finding problem
Publication
, Journal Article
Maggs, BM; Plotkin, SA
Published in: Information Processing Letters
January 25, 1988
In this paper we show that the minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a nonrecursive algorithm for finding minimum-cost spanning trees on mesh-connected computers which has the same asymptotic running time as but is much simpler than the previous recursive algorithms. © 1988.
Duke Scholars
Published In
Information Processing Letters
DOI
ISSN
0020-0190
Publication Date
January 25, 1988
Volume
26
Issue
6
Start / End Page
291 / 293
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 40 Engineering
- 09 Engineering
- 08 Information and Computing Sciences
- 01 Mathematical Sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Maggs, B. M., & Plotkin, S. A. (1988). Minimum-cost spanning tree as a path-finding problem. Information Processing Letters, 26(6), 291–293. https://doi.org/10.1016/0020-0190(88)90185-8
Maggs, B. M., and S. A. Plotkin. “Minimum-cost spanning tree as a path-finding problem.” Information Processing Letters 26, no. 6 (January 25, 1988): 291–93. https://doi.org/10.1016/0020-0190(88)90185-8.
Maggs BM, Plotkin SA. Minimum-cost spanning tree as a path-finding problem. Information Processing Letters. 1988 Jan 25;26(6):291–3.
Maggs, B. M., and S. A. Plotkin. “Minimum-cost spanning tree as a path-finding problem.” Information Processing Letters, vol. 26, no. 6, Jan. 1988, pp. 291–93. Scopus, doi:10.1016/0020-0190(88)90185-8.
Maggs BM, Plotkin SA. Minimum-cost spanning tree as a path-finding problem. Information Processing Letters. 1988 Jan 25;26(6):291–293.
Published In
Information Processing Letters
DOI
ISSN
0020-0190
Publication Date
January 25, 1988
Volume
26
Issue
6
Start / End Page
291 / 293
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 40 Engineering
- 09 Engineering
- 08 Information and Computing Sciences
- 01 Mathematical Sciences