Back to Search
Start Over
LEHMAN'S THEOREM AND THE DIRECTED STEINER TREE PROBLEM.
- Source :
-
SIAM Journal on Discrete Mathematics . 2016, Vol. 30 Issue 1, p141-153. 13p. - Publication Year :
- 2016
-
Abstract
- In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403-417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 30
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 114761081
- Full Text :
- https://doi.org/10.1137/15M1007185