The Steiner Tree Page
Library Home || Full Table of Contents || Suggest a Link || Library Help
|The Steiner tree problem is a minimum interconnection problem. The most basic version is in a graph: given a weighted graph in which a subset of vertices are identified as terminals, find a minimum-weight connected subgraph that includes all the terminals. If the edge weights are all positive, then the resulting subgraph is obviously a tree. The problem can also be applied in the geometric realm; the two most common variants are the Euclidean Steiner tree and rectilinear Steiner tree problems. People, open problems, and a bibliography.|
|Resource Types:||Problems/Puzzles, Books, Bibliographies|
|Math Topics:||Graph Theory|
© 1994- The Math Forum at NCTM. All rights reserved.