next up previous
Next: 1 Introduction

Minimum-Cost Spanning Tree as a Path-Finding Problem

Bruce M. Maggs - Serge A. Plotkin

Laboratory for Computer Science
Cambridge MA 02139

Sun Jul 21 23:36:02 EDT 1996


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

Bruce Maggs
Sun Jul 21 23:35:52 EDT 1996
anonymous logging image