Definition:
A minimum-weight tree connecting a designated set of vertices, called terminals, in a weighted graph or points in a space. The tree may include non-terminals, which are called Steiner vertices or Steiner points.
Explanation
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.
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.
Example
Input: Set of arbitrary points to be connected. Imagine each point is a computer that must be connected to a network, using as little wire as possible.
+--------------------------+
| |
| |
| o o |
| |
| |
| |
| |
| |
| o o |
| |
| o o |
| |
+--------------------------+
Output:The solution. Note this solution is far from exact. ASCII art is a little less precise than CAD, which is what would probably be used in a real-world application.
+--------------------------+
| |
| |
| o o |
| \_____/ |
| | |
| | |
| | |
| _|_ |
| / \ |
| o_______/ \_______o |
| / \ |
| o o |
| |
+--------------------------+
Works Cited
- http://www.nist.gov/dads/HTML/steinertree.html
- http://ganley.org/steiner/intro.html
- http://www.cs.sunysb.edu/~algorith/files/steiner-tree.shtml