Minimum-Cost Spanning Tree as a Path-Finding Problem

Bruce M. Maggs - Serge A. Plotkin

Laboratory for Computer Science
MIT
Cambridge MA 02139

Sun Jul 21 23:36:02 EDT 1996

Abstract:

In this paper we show that minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a non-recursive algorithm for finding minimum-cost spanning trees on mesh-connected computers that has the same asymptotic running time but is much simpler than the previous recursive algorithms.

7pt 10pt

• 1 Introduction
• 2 Minimum-cost spanning tree
• 3 Implementation on a mesh-connected computer
• 4 Acknowledgments
• References
• About this document ...