Banazîr the Jedi Hobbit (banazir) wrote,
Banazîr the Jedi Hobbit

  • Mood:

Steiner Tree Problems

The Steiner tree problem, named after Jakob Steiner (1796 - 1863), is a problem in combinatorial optimization.

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 original problem was stated in the form that has become known as the Euclidean Steiner tree problem: Given N points in the plane, it is required to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments...

The most general version is Steiner tree in graphs: Given a weighted graph G(V,E,w) and subset S of its vertices, find a tree of minimal weight which includes all vertices in S.

The Steiner tree problem has applications in circuit layout or network design. Most versions of the Steiner tree problem are NP-complete, i.e., thought to be computationally hard. 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.

                    -excerpted and adapted from Wikipedia

This is another problem family that colleagues in Electrical Engineering and Computer Engineering introduced me to.

The Steiner Tree Page created by Joe Ganley is a (no longer maintained) repository of links to various sites, algorithms and implementations such as GeoSteiner by Warme et al., and catalogs of variants.

Has anyone reading this done a project on Steiner trees, or is anyone currently working on related problems and interested in the topic?


  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.