Minimum Spanning Tree Problem

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin

ABSTRACT

The minimum spanning tree problem is perhaps the simplest, and certainly one of the most central, models in the field of network optimization. The minimum spanning tree problem arises in a number of applications, both as a stand-alone problem and as a subproblem in more complex problem settings. We described several applications of the minimum spanning tree problem in Chapter 8.1. In this article, we first consider combinatorial-based optimality conditions for assessing whether a given spanning tree is a minimum spanning tree. We consider two such optimality conditions--path and cut optimality conditions. We then describe two algorithms, Kruskal's algorithm and Prim's algorithm, based upon these optimality conditions. We illustrate these algorithms using numerical examples and also analyze their worst-case complexity.