Steiner Minimal Trees

While a spanning tree spans all vertices of a given graph, a Steiner tree spans a given subset of vertices. In the Steiner minimal tree problem, the vertices are divided into two parts: terminals and nonterminal vertices. The terminals are the given vertices which must be included in the solution. The cost of a Steiner tree is defined as the total edge weight. A Steiner tree may contain some nonterminal vertices to reduce the cost. Let V be a set of vertices. In general, we are given a set L ⊂ V of terminals and a metric defining the distance between any two vertices in V. The objective is to find a connected subgraph spanning all the terminals of minimal total cost. Since the distances are all nonnegative in a metric, the solution is a tree structure. Depending on the given metric, two versions of the Steiner tree problem have been studied. • (Graph) Steiner minimal trees (SMT): In this version, the vertex set and metric is given by a finite graph. • Euclidean Steiner minimal trees (Euclidean SMT): In this version, V is the entire Euclidean space and thus infinite. Usually the metric is given by the Euclidean distance (L2-norm). That is, for two points with coordinates (x1, y2) and (x2, y2), the distance is√ (x1 − x2)2 + (y1 − y2)2. In some applications such as VLSI routing, L1-norm, also known as rectilinear distance, is used, in which the distance is defined as |x1 − x2|+ |y1 − y2|. Figure 1 illustrates a Euclidean Steiner minimal tree and a graph Steiner minimal tree. 1.1 Approximation by MST Let G = (V,E,w) be an undirected graph with nonnegative edge weights. Given a set L ⊂ V of terminals, a Steiner minimal tree is the tree T ⊂ G of minimum total edge weight such that T includes all vertices in L. Problem: Graph Steiner Minimal Tree Instance: A graph G = (V,E,w) and a set L ⊂ V of terminals Goal: Find a tree T with L ⊂ V (T) so as to minimize w(T)