The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.
The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices.
The Steiner tree problem has applications in circuit layout or network design. Most versions of the Steiner tree problem are NP-complete. In fact, one of these was among Karp's original 21 NP-complete problems. Some restricted cases can be solved in polynomial time. In practice, heuristics are used.
Read more about Steiner Tree Problem: Euclidean Steiner Tree, Rectilinear Steiner Tree, Generalization of Minimum Steiner Tree, Steiner Ratio
Famous quotes containing the words steiner, tree and/or problem:
“To many men ... the miasma of peace seems more suffocating than the bracing air of war.”
—George Steiner (b. 1929)
“Happy are those who find wisdom, and those who get understanding, for her income is better than silver, and her revenue better than gold. She is more precious than jewels, and nothing you desire can compare with her. Long life is in her right hand; in her left hand are riches and honor. Her ways are ways of pleasantness, and all her paths are peace. She is a tree of life to those who lay hold of her; those who hold her fast are called happy.”
—Bible: Hebrew, Proverbs 3:13-18.
“The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
—Lawrence Kutner (20th century)