The Steiner tree problem (STP) in graphs is one of the most studied problems in
combinatorial optimization. Since its inception in 1970, numerous articles published in the …

Publisher Summary This chapter reviews formulations and some procedures that have been
suggested for the solution of the Steiner Problem in graphs. It presents the definition and …

We give a survey up to 1989 on the Steiner tree problems which include the four important
cases of euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We …

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 …

We give the first approximation algorithm for the generalized network Steiner problem, a
problem in network design. An instance consists of a network with link-costs and} for each …

The problem of determining a minimum cost connected network (ie, weighted graph) G that
spans a given subset of vertices is known in the literature as the Steiner problem in …

This paper is intended as a survey in the area of network synthesis and optimum network
design, which, in view of the importance and variety of the underlying applications, has …

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that
connects a root node to every node in a designated node set V. We give a dual ascent …

In this paper, we present the implementation of a branch‐and‐cut algorithm for solving
Steiner tree problems in graphs. Our algorithm is based on an integer programming …

Abstract The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and
vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the …