[Zurück]

L. Gouveia, M. Leitner, I. Ljubic:
"Hop Constrained Steiner Trees with multiple Root Nodes";
European Journal of Operational Research, 236 (2014), 1; S. 100 - 112.

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree
problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing
roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the
number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H.
The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes.
This article proposes integer linear programming models utilizing one layered graph for each root node.
Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening
inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously
proposed flow- and path-based formulations are given. To solve the problem to optimality, we
implement branch-and-cut algorithms for the layered graph formulations. Our computational study
shows their clear advantages over previously existing approaches.

http://dx.doi.org/10.1016/j.ejor.2013.11.029

http://publik.tuwien.ac.at/files/PubDat_225626.pdf