Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for \(d \in \{3, 4, 5\}\), whose Hanan grids contain up to several millions of edges.     

Rotationally optimal spanning and Steiner trees in uniform orientation metrics

We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees.     

A deep-submicron steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for the generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as “Deep-submicron Steiner tree”, as minimizing the number of Steiner nodes is crucial for signal integrity issues in deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The idea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nodes) tree of small cost.The simulation results show the high efficiency of our approach.     

Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

The rectilinear Steiner tree problem is to find a minimum-length rectilinear interconnection of a set of points in the plane. A reduction from the rectilinear Steiner tree problem to the graph Steiner tree problem allows the use of exact algorithms for the graph Steiner tree problem to solve the rectilinear problem. Furthermore, a number of more direct, geometric algorithms have been devised for computing optimal rectilinear Steiner trees. This paper surveys algorithms for computing optimal rectilinear Steiner trees and presents experimental results comparing nine of them: graph Steiner tree algorithms due to Beasley, Bern, Dreyfus and Wagner, Hakimi, and Shore, Foulds, and Gibbons and geometric algorithms due to Ganley and Cohoon, Salowe and Warme, and Thomborson, Alpern, and Carter.     

The rectilinear class Steiner tree problem for intervals on two parallel lines

We consider a generalization of the Rectilinear Steiner Tree problem, where our input is classes of required points instead of simple required points. Our task is to find a minimum rectilinear tree connecting at least one point from each class. We prove that the version, where all required points lie on two parallel lines, called Rectilinear Class Steiner Tree (channel) problem, is NP-hard. But we give a linear time algorithm for the case where the points of each required class are clustered, and the classes consist of non overlapping intervals of points.Part of this research was conducted while the author was attending a research initiative at the Leonardo Fibonacci Institute, Povo, Italy.     

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.     

Minimal curvature-constrained networks

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon.     

Gradient-Constrained Minimum Networks. III. Fixed Topology

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).     

Vertex-Disjoint Packing of Two Steiner Trees: polyhedra and branch-and-cut

Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes. Received: August 1999 / Accepted: January 2001?Published online April 12, 2001     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.