Back to Search
Start Over
DESIGNING STEINER NETWORKS WITH UNICYCLIC CONNECTED COMPONENTS: AN EASY PROBLEM.
- Source :
-
SIAM Journal on Discrete Mathematics . 2010, Vol. 24 Issue 4, p1541-1557. 17p. - Publication Year :
- 2010
-
Abstract
- This paper focuses on the design of minimum-cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of two known problems: the perfect binary 2-matching problem and the problem of computing a minimum-weight basis of the bicircular matroid. It turns out that the problem is polynomially solvable. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the Padberg-Rao algorithm to separate blossom inequalities. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 24
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 64279010
- Full Text :
- https://doi.org/10.1137/090759033