The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.5.10 Steiner Tree

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A graph G=(V,E). A subset of vertices T \in V.

Problem: Find the smallest tree connecting all the vertices of T.

Excerpt from The Algorithm Design Manual: Steiner tree often arises in network design and wiring layout problems. Suppose we are given a set of sites that must be connected by wires as cheaply as possible. The minimum Steiner tree describes the way to connect them using the smallest amount of wire. Analogous problems arise in designing networks of water pipes or heating ducts in buildings. Similar considerations also arise in VLSI circuit layout, where we seek to connect a set of sites to (say) ground under constraints such as material cost, signal propagation time, or reducing capacitance.

The Steiner tree problem is distinguished from the minimum spanning tree problem in that we are permitted to construct or select intermediate connection points to reduce the cost of the tree.


Implementations

  • GeoSteiner: Software for Computing Steiner Trees (C) (rating 10)
  • FLUTE: Fast Lookup Table Based Technique for RSMT Construction and Wirelength Estimation (C) (rating 9)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 8)
  • PHYLIP -- inferring phylogenic trees (C,Pascal) (rating 7)
  • Salowe's Rectilinear Steiner trees (C) (rating 5)

  • Recommended Books

    The Steiner Tree Problem: a tour through graphs, algorithms, and complexity by Hans Jurgen Promel, Angelika Steger Advances in Steiner Trees by D. Du and J. Smith and J. Rubinstein The Steiner Tree Problem by R. Hwang and D. Richards and P. Winter
    Computational Geometry by F. Preparata and M. Shamos Graph Algorithms by S. Even Combinatorial Optimization: Networks and Matroids by E. Lawler

    Related Links

  • COIN|OR: COmputational INfrastructure for Operations Research

    Related Problems


      
    Minimum Spanning Tree
      
    Shortest Path



    This page last modified on 2008-07-10 .
    www.algorist.com