In the classical geometric Steiner tree problem, we are given a set of points in the plane and our aim is to find the shortest network interconnecting the set of points. An unlimited number of additional vertices, called Steiner points, may be added to shorten the network. In the minimum k -Steiner tree problem, the number of Steiner points is limited to some nonnegative integer k , which creates additional complexity. This paper improves on the current algorithmic approach to solving the Euclidean k -Steiner tree problem. We introduce a novel pruning test and strengthen existing tests to allow more extensive elimination of sub-optimal topologies during the generation phase of the algorithm. We also introduce a new ILP model for the concatenation phase. Finally, we present experimental results that demonstrate the effectiveness of these novel components.

The Euclidean k-Steiner tree problem asks for a minimum-cost network connecting n given points in the plane, allowing at most k additional nodes referred to as Steiner points. In the classical Steiner tree problem in which there is no restriction on the number of nodes, every Steiner point must be of degree 3. The k-Steiner problem differs in that Steiner points of degree 4 may be included in an optimal solution. This simple change leads to a number of complexities when attempting to create a generation algorithm for optimal k-Steiner trees, which has proven to be a powerful component of the flagship algorithm, namely GeoSteiner, for solving the classical Steiner tree problem. In the present paper we firstly extend the basic framework of GeoSteiner's generation algorithm to include degree-4 Steiner points. We then introduce a number of novel results restricting the structural and geometric properties of optimal k-Steiner trees, and then show how these properties may be used as topological pruning methods underpinning our generation algorithm. Finally, we present experimental data to show the effectiveness of our pruning methods in reducing the number of sub-optimal solution topologies.

Abstract We introduce a formal framework for the study of augmenting networks in the plane for disaster‐resilience, where a disaster is modeled by a straight‐line segment. We generalize various graph structures from classical 2‐edge‐connectivity, including minimal cuts and blocks. The key concept that we introduce is that of an ‐leaf, which builds on the fundamental “leaf‐block” concept from classical augmentation. We present a number of algorithms for constructing the above‐mentioned graph structures, including a sweep‐line algorithm that finds all edge‐cuts that can be destroyed by a single disaster. We also present an algorithm which optimally adds a single edge between a pair of ‐leaves or blocks while avoiding certain disaster regions. Finally, we present a number of heuristic schemes for solving the disaster‐resilient network augmentation problem and perform extensive experiments to demonstrate the power of the ‐leaf concept within heuristic design.

Abstract We present methods for simplifying the geometry of polygonal obstacles as a preprocessing step to solving obstacle‐avoiding Steiner network problems in the plane. The methods reduce the total number of vertices and edges that need to be considered for the given obstacles, and their use is expected to significantly improve the efficiency of exact algorithms for solving a range of practical Steiner network problems in obstacle environments. Included are methods forextendingobstacles (via a newpaddingmethod and abackfillingprocedure from the literature), and various methods for simplifying obstacles, including new methods calledboundingandeliminating. We show that these methods reduce the total number of obstacle vertices and edges by performing experiments on obstacles with up to 100 vertices in the presence of up to 100 terminals. The experiments utilize a modified version of a known algorithm for quickly generating large numbers of “random” polygons with hundreds of vertices. Corresponding datasets and implementations have been made available on GitHub.

Relay node placement, which aims to connect pre-deployed sensor nodes to base stations, is essential in minimizing the costs of wireless sensor networks. In this paper, we formulate the new Node-Weighted Partial Terminal Steiner Tree Problem (NWPTSTP) for minimum-cost relay node placement in two-tiered wireless sensor networks. The objective is to minimize the sum of heterogeneous production and placement costs of relay nodes and the sum of outage probabilities of transmission routes in a routing tree simultaneously. This extends the previous work that considers the costs of relay nodes to be homogeneous. After formulating NWPTSTP for this purpose, we prove that it can be transformed to the existing node-weighted Steiner tree problem. Subsequently, we conduct some theoretical analyses on the emerging Physarum-inspired algorithms to reveal their potential of computing Steiner trees. Based on these analyses, we propose a new Physarum-inspired algorithm for solving NWPTSTP. We conduct computational trials to show that: 1) in comparison to a state-of-the-art approximation algorithm for solving the node-weighted Steiner tree problem, our Physarum-inspired algorithm can produce better solutions in a smaller amount of time; and 2) in comparison to two state-of-the-art relay node placement algorithms, our Physarum-inspired algorithm can design wireless sensor networks with 25% lower relay cost and similar quality of service (specifically, 5% shorter network lifetime, 2% longer delay, and 0% loss of goodput). This indicates the usefulness of our Physarum-inspired algorithm for minimum-cost relay node placement in budget-limited scenarios.

Abstract We present a new exact algorithm for computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2‐edge‐connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2‐edge‐connected Steiner network problem.

It is challenging to design large and low-cost communication networks. In this paper, we formulate this challenge as the prize-collecting Steiner Tree Problem (PCSTP). The objective is to minimize the costs of transmission routes and the disconnected monetary or informational profits. Initially, we note that the PCSTP is MAX SNP-hard. Then, we propose some post-processing techniques to improve suboptimal solutions to PCSTP. Based on these techniques, we propose two fast heuristic algorithms: the first one is a quasilinear time heuristic algorithm that is faster and consumes less memory than other algorithms; and the second one is an improvement of a state-of-the-art polynomial time heuristic algorithm that can find high-quality solutions at a speed that is only inferior to the first one. We demonstrate the competitiveness of our heuristic algorithms by comparing them with the state-of-the-art ones on the largest existing benchmark instances (169 800 vertices and 338 551 edges). Moreover, we generate new instances that are even larger (1 000 000 vertices and 10 000 000 edges) to further demonstrate their advantages in large networks. The state-of-the-art algorithms are too slow to find high-quality solutions for instances of this size, whereas our new heuristic algorithms can do this in around 6 to 45s on a personal computer. Ultimately, we apply our post-processing techniques to update the best-known solution for a notoriously difficult benchmark instance to show that they can improve near-optimal solutions to PCSTP. In conclusion, we demonstrate the usefulness of our heuristic algorithms and post-processing techniques for designing large and low-cost communication networks.

We introduce a flow‐dependent version of the quadratic Steiner tree problem in the plane. An instance of the problem on a set of embedded sources and a sink asks for a directed tree T spanning of these nodes and a bounded number of Steiner points, such that is a minimum, where f(e) is the flow on edge e. The edges are uncapacitated and the flows are determined additively, that is, the flow on an edge leaving a node u will be the sum of the flows on all edges entering u. Our motivation for studying this problem is its utility as a model for relay augmentation of wireless sensor networks. In these scenarios, one seeks to optimize power consumption—which is predominantly due to communication and, in free space, is proportional to the square of transmission distance—in the network by introducing additional relays. We prove several geometric and combinatorial results on the structure of optimal and locally optimal solution‐trees (under various strategies for bounding the number of Steiner points) and describe a geometric linear‐time algorithm for constructing such trees with known topologies. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 18–28 2014

Abstract We investigate the problem of designing a minimum‐cost flow network interconnecting n sources and a single sink, each with known locations in a normed space and with associated flow demands. The network may contain any finite number of additional unprescribed nodes from the space; these are known as the Steiner points. For concave increasing cost functions, a minimum‐cost network of this sort has a tree topology, and hence can be called a Minimum Gilbert Arborescence (MGA). We characterize the local topological structure of Steiner points in MGAs, showing, in particular, that for a wide range of metrics, and for some typical real‐world cost functions, the degree of each Steiner point is 3. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract Given a set of points, we define a minimum Steiner point tree to be a tree interconnecting these points and possibly some additional points such that the length of every edge is at most 1 and the number of additional points is minimized. We propose using Steiner minimal trees to approximate minimum Steiner point trees. It is shown that in arbitrary metric spaces this gives a performance difference of at most 2n‐ 4, wherenis the number of terminals. We show that this difference is best possible in the Euclidean plane, but not in Minkowski planes with parallelogram unit balls. We also introduce a new canonical form for minimum Steiner point trees in the Euclidean plane; this demonstrates that minimum Steiner point trees are shortest total length trees with a certain discrete‐edge‐length condition. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract We suggest a novel distance‐based method for the determination of phylogenetic trees. It is based on multidimensional scaling and Euclidean Steiner trees in high‐dimensional spaces. Preliminary computational experience shows that the use of Euclidean Steiner trees for finding phylogenetic trees is a viable approach. Experiments also indicate that the new method is comparable with results produced by neighbor joining (Saitou and Nei, Mol Biol Evol 4 (1987), 406–425). © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Node localisation in wireless sensor networks is a difficult problem due to the large number of parameters to be estimated and the nonlinear relationship between the measurements and the parameters. Assuming the presence of a number of anchor nodes with known positions and a centralised architecture, a Bayesian algorithm for node localisation in wireless sensor networks is proposed. The algorithm is a refinement of an existing importance sampling method referred to as progressive correction. A simulation analysis shows that, with only a few anchor nodes, the proposed method is capable of accurately localising a large number of nodes.

Abstract Efficient methods to model and optimize the design of open‐cut mines have been known for many years. The design of the infrastructure of underground mines has a similar potential for optimization and strategic planning. In this article we discuss the use of network optimization to tackle this problem. The idea is to design a connected system of declines, ramps, drives, and possibly shafts, to minimize capital development and haulage costs over the lifetime of a mine. This can be modeled as a variation on the Steiner problem, with suitable metric and constraints. These constraints include: an upper bound on the absolute gradient of arcs in the embedded network (typically 1/7), turning circle restrictions for navigability, and obstacle avoidance. Here we give an overview of the literature, focussing on our published work. We investigate the way in which this design problem can be modeled as a network optimization problem that accurately reflects the real costs involved while remaining mathematically tractable. Our approach is to first establish a fundamental model, which principally captures the development costs of the mine, and to study its geometric properties. We then outline more complicated generalized models, which add extra costs and constraints to the fundamental model but are still solvable. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 40–50 2007

Abstract We present some fundamental flexibility properties for minimum length networks (known as Steiner minimum trees) interconnecting a given set of points in an environment in which edge segments are restricted to λ uniformly oriented directions. These networks are referred to as λ‐SMTs. They promise to play an increasingly important role in the future of optimal wire routing in VLSI physical design, particularly for the next generation of VLSI circuits. In this article we develop the concept of a flexibility polygon for a λ‐SMT, which is a region representing the union of all λ‐SMTs with the same topology on a given set of points. We show that this polygon can be constructed, for a given point set and given topology, in linear time. We discuss some of the future applications of this polygon, which can be thought of as a geometric representation of the amount of flexibility inherent in a given λ‐SMT. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 142–153 2005

Abstract The Steiner problem in the λ‐plane is the problem of constructing a minimum network connecting a given set of nodes (called terminals), with the constraint that all line segments have slopes chosen from the λ uniform orientation angles ω, 2ω, … , λω, where ω = π/λ. This problem appears to be substantially harder than either the Euclidean or rectilinear Steiner problem, as there can be many different λ‐networks that have the same topology and terminal set, but are locally minimal with respect to the perturbation of single Steiner points. In this paper, we show that there are large classes of such networks that cannot be minimum because they necessarily contain subpaths that can be perturbed to shorten the length of the network. These classes are defined in terms only of the angles between edges in the paths and not edge lengths. Using largely geometric methods, we give a complete classification of these “forbidden paths.” This classification will be a crucial element in devising a pruning process for future efficient exact algorithms for solving the Steiner problem in the λ‐plane. © 2002 Wiley Periodicals, Inc.

In this paper we use the variational method to systematically study properties of minimum networks connecting any given set of points (called terminals) in a $\lambda$-plane, in which all lines are in $\lambda$ uniform orientations $i\pi /\lambda\ (0\le i < \lambda )$. We prove a number of angle conditions for Steiner minimum $\lambda$-trees, which are similar to the ones in the Euclidean case. In particular, we show that there exists a Steiner minimum $\lambda$-tree whose minimum angles at Steiner points are $\lfloor 2\lambda /3\rfloor\pi /\lambda$ and whose maximum angles are $\lceil 2\lambda /3\rceil\pi /\lambda$. We also investigate the assignment of nonstraight edges and unequal angles in Steiner minimum $\lambda$-trees, and we prove that there exists a Steiner minimum $\lambda$-tree in which every full component has at most one nonstraight edge. From these properties we are able to devise a number of finite methods for constructing Steiner minimum $\lambda$-trees. One of these methods is based on using algorithms for finding graphical Steiner minimum trees, and the other uses a generalization of the method of Melzak for Euclidean Steiner trees.

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectilinear Steiner problem for the case where terminals are constrained to lie on almost any fixed set of simple disjoint compact curves. © 1999 John Wiley & Sons, Inc. Networks 33: 145–155, 1999