Directed Steiner problems with connectivity constraints
G Dahl - Discrete applied mathematics, 1993 - Elsevier
Discrete applied mathematics, 1993•Elsevier
We present a generalization of the Steiner problem in a directed graph. Given nonnegative
weights on the arcs, the problem is to find a minimum weight subset F of the arc set such that
the subgraph induced by F contains a given number of arc-disjoint directed paths from a
certain root node to each given terminal node. Some applications of the problem are
discussed and properties of associated polyhedra are studied. Results from a cutting plane
algorithm are reported.
weights on the arcs, the problem is to find a minimum weight subset F of the arc set such that
the subgraph induced by F contains a given number of arc-disjoint directed paths from a
certain root node to each given terminal node. Some applications of the problem are
discussed and properties of associated polyhedra are studied. Results from a cutting plane
algorithm are reported.
Abstract
We present a generalization of the Steiner problem in a directed graph. Given nonnegative weights on the arcs, the problem is to find a minimum weight subset F of the arc set such that the subgraph induced by F contains a given number of arc-disjoint directed paths from a certain root node to each given terminal node. Some applications of the problem are discussed and properties of associated polyhedra are studied. Results from a cutting plane algorithm are reported.
Elsevier