ganley.org -> The Steiner Tree Page -> Introduction

Introduction


The Steiner tree problem, succintly, 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. Here, the input is a set of points in space that are the terminals, and the objective is to compute a tree of minimum length (in the appropriate metric) that connects all the terminals. In addition to the Euclidean and rectilinear metrics, the hexagonal and octagonal metrics have been considered. More recently, researchers have considered Steiner trees that minimize certain estimates of electrical delay and other objectives.

For more introductory information, probably the best general reference is the book The Steiner Tree Problem, by Frank Hwang, Dana Richards, and Pawel Winter. This is number 53 in North-Holland's Annals of Discrete Mathematics series. You can go to the "Bookstore" to order this book from Fatbrain.com.