- Minimum-cost spanning tree as a path-finding
problem. B. M. Maggs and S. A. Plotkin, Information Processing
Letters, Vol. 26, No. 6, January 1988, pp. 291-293.
- In this paper we show that minimum-cost spanning tree is an instance
of the algebraic path problem (also known as the closed-semiring
path-finding problem). This observation yields a non-recursive
algorithm for finding the minimum-cost spanning tree of an N-node
graph on an N-by-N mesh-connected computer in O(N) time. The algorithm
has the same running time as previously-known recursive algorithms,
but it is much simpler.
- Back to other
- Back to my home page