1.4.3 Minimum Spanning Tree

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A graph G = (V,E) with weighted edges.

Problem: The subset of E of G of minimum weight which forms a tree on V.

Excerpt from The Algorithm Design Manual: The minimum spanning tree (MST) of a graph defines the cheapest subset of edges that keeps the graph in one connected component. Telephone companies are particularly interested in minimum spanning trees, because the minimum spanning tree of a set of sites defines the wiring scheme that connects the sites using as little wire as possible. It is the mother of all network design problems. Minimum spanning trees prove important for several reasons:

The best book available for this problem is Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.


Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 5)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • The Stanford GraphBase (C) (rating 4)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)
  • Discrete Optimization Methods (Pascal) (rating 3)
  • Algorithms in C++ -- Sedgewick (C++) (rating 3)
  • Combinatorica (Mathematica) (rating 3)

    Related Problems

  • Set Data Structures
  • Steiner Tree
  • Traveling Salesman Problem


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .