• 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.

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page