Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems

This article introduces new reduction techniques for the Steiner tree problem in graphs (SPG) and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. In particular, we introduce a generalization of the Steiner bottleneck distance—the arguably most important reduction concept for SPG. While … Read more

A Simulated Annealing Algorithm for the Directed Steiner Tree Problem

In \cite{siebert2019linear} the authors present a set of integer programs (IPs) for the Steiner tree problem, which can be used for both, the directed and the undirected setting of the problem. Each IP finds an optimal Steiner tree with a specific structure. A solution with the lowest cost, corresponds to an optimal solution to the … Read more

A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is … Read more

Exact algorithms for bi-objective ring tree problems with reliability measures

We introduce bi-objective models for ring tree network design with a focus on network reliability within telecommunication applications. Our approaches generalize the capacitated ring tree problem (CRTP) which asks for a partially reliable topology that connects customers with different security requirements to a depot node by combined ring and tree graphs. While the CRTP aims … Read more

Steiner Trees with Degree Constraints: Structural Results and an Exact Solution Approach

In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner … Read more

Chance-Constrained Multi-Terminal Network Design Problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose a scenario-based Steiner cut formulation, and a … Read more

An improved algorithm for computing Steiner minimal trees in Euclidean d-space

We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology … Read more

Solving Steiner tree problems in graphs with Lagrangian relaxation

This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due … Read more