Facets of the (s,t)-p-path polytope
Please always quote using this URN: urn:nbn:de:0297-zib-9328
- \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope.
Download full text files
Additional Services
| Author: | Rüdiger Stephan |
|---|---|
| Document Type: | ZIB-Report |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
| Date of first Publication: | 2006/07/03 |
| Series (Serial Number): | ZIB-Report (06-38) |
| ZIB-Reportnumber: | 06-38 |
| Published in: | Appeared in: Discrete Appl. Math. 157(14), 2009, pp. 3119-3132 |
