Name
Abstract | ||
|---|---|---|
The purpose of this study is to provide a polyhedral analysis of the p-cycle polytope, which is the convex hull of the incidence vectors of all the p-cycles (simple directed cycles consisting of p arcs) of the complete directed graph Kn. We first determine the dimension of the p-cycle, polytope, characterize the bases of its equality set, and prove two lifting results. We then describe several classes of valid inequalities for the case 2<p<n, together with necessary and sufficient conditions for these inequalities to induce facets of the p-cycle polytope. We also briefly discuss the complexity of the associated separation problems. Finally, we investigate the relationship between the p-cycle polytope and related polytopes, including the p-circuit polytope. Since the undirected versions of symmetric inequalities which induce facets of the p-cycle polytope are facet-inducing for the p-circuit polytope, we obtain new classes of facet-inducing inequalities for the p-circuit polytope. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0166-218X(00)00314-0 | Discrete Applied Mathematics |
Keywords | Field | DocType |
directed graph,traveling salesman,convex hull | Discrete mathematics,Birkhoff polytope,Combinatorics,Ehrhart polynomial,Permutohedron,Uniform k 21 polytope,Convex polytope,Cross-polytope,Vertex enumeration problem,Mathematics,Polyhedral combinatorics | Journal |
Volume | Issue | ISSN |
112 | 1-3 | 0166-218X |
Citations | PageRank | References |
6 | 0.61 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark E. Hartmann | 1 | 23 | 3.03 |
| Ozgur Ozluk | 2 | 56 | 8.92 |