Steiner minimal trees for regular polygons

Fifty years ago Jarnik and Kössler showed that a Steiner minimal tree for the vertices of a regularn-gon contains Steiner points for 3 n5 and contains no Steiner point forn=6 andn13. We complete the story by showing that the case for 7n12 is the same asn13. We also show that the set ofn equally spaced points yields the longest Steiner minimal tree among all sets ofn cocircular points on a given circle.     

Steiner minimal trees for bar waves

A Steiner minimal tree (SMT) for a set of pointsP in the plane is a shortest network interconnectingP. The construction of a SMT for a general setP is known to be anNP-complete problem. Recently, SMTs have been constructed for special setsP such as ladders, splitting trees, zigzag lines and co-circular points. In this paper we study SMTs for a wide class of point-sets called mild bar wave. We show that a SMT for a mild bar wave must assume a special form, thus the number of trees needed to be inspected is greatly reduced. Furthermore if a mild bar wave is also a mild rectangular wave, then we produce a Steiner tree constructible in linear time whose length can exceed that of a SMT by an amount bounded by the difference in heights of the two endpoints of the rectangular wave, thus independent of the number of points. When a rectangular wave satisfies some other conditions (including ladders as special cases), then the Steiner tree we produced is indeed a SMT.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

On Steiner trees for bounded point sets

Geometriae Dedicata -     

A decomposition theorem on Euclidean Steiner minimal trees

The Euclidean Steiner minimal tree problem is known to be an NP-complete problem and current alogorithms cannot solve problems with more than 30 points. Thus decomposition theorems can be very helpful in extending the boundary of workable problems. There have been only two known decomposition theorems in the literature. This paper provides a 50% increase in the reservoir of decomposition theorems.     

A simple proof of Hwang's theorem for rectilinear Steiner minimal trees

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: LetS be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree forS has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight linel, and the tree edges incident to the Steiner points onl appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

On component-size bounded Steiner trees

A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.     

Class Steiner trees and VLSI-design

We consider a generalized version of the Steiner problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with required classes of vertices and Steiner vertices, find a shortest connected subgraph containing at least one vertex of each required class. We show that this problem is NP-hard, even if there are no Steiner vertices and the graph is a tree. Moreover, the same complexity result holds if the input class Steiner graph additionally is embedded in a unit grid, if each vertex has degree at most three, and each class consists of no more than three vertices. For similar restricted versions, we prove MAX SNP-hardness and we show that there exists no polynomial-time approximation algorithm with a constant bound on the relative error, unless P = NP. We propose two efficient heuristics computing different approximate solutions in time O(¦E¦+¦V¦log¦V¦) and in time O(c(¦E¦+¦V¦log¦V¦)), respectively, where E is the set of edges in the given graph, V is the set of vertices, and c is the number of classes. We present some promising implementation results. kw]Steiner Tree; Heuristic; Approximation complexity; MAX-SNP-hardness     

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Recently, Byrka, Grandoni, Rothvoß and Sanità gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm.     

带梯子的曲折线上的最短树问题

Abstract. In this paper,Steiner minimal trees for point sets with special structure are studied.These sets consist of zigzag lines and equidistant points lying on them.     

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

On Steiner trees and minimum spanning trees in hypergraphs

The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

An analytical method for derivation of the Steiner Ratio of 3D euclidean Steiner trees

We stress the convenience of some analytical methods which have been introduced recently [Mondaini, R. P.: In: Nonconvex Optimization and its Applications series, pp. 373–390. Kluwer Acad. (2003); Mondaini, R. P.: In: BIOMAT 2005, International Symposium on Mathematical and Computational Biology, pp. 327–342. World Scientific Co Ltd (2006)] for calculating the Steiner Ratio of finite sets of points in ${\mathbb{R}}^3$ . These methods are good enough at reproducing the results obtained by reduction of the search space of numerical algorithms and can be easily extended to any number of dimensions.     

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that $|W|=k$, for a fixed positive integer k. The enumeration is performed within $O(n)$ delay, where $n=|V(G)|$ consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset $W\subseteq V(G)$ can be computed in polynomial time, provided that the size of W is bounded by a constant.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.