Facets of the \(p\)-cycle polytope

DOI10.1016/S0166-218X(00)00314-0zbMath1009.52025OpenAlexW2146150616MaRDI QIDQ5946821

Özgür Özlük, Mark E. Hartmann

Publication date: 30 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00314-0

zbMATH Keywords

\(p\)-circuit\(p\)-cycle\(p\)-mediancycle polytopetraveling salesman problem (TSP)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs ⋮ Cycle selections ⋮ On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ On cardinality constrained cycle and path polytopes ⋮ Facets of the \((s,t)-p\)-path polytope ⋮ Facets of the \(p\)-cycle polytope ⋮ On the cycle polytope of a directed graph and its relaxations ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming ⋮ On the facets and diameter of thek-cycle polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parametric shortest path algorithms with an application to cyclic staffing
• Balancing problems in acyclic networks
• The median tour and maximal covering tour problems: Formulations and heuristics
• Clique tree inequalities define facets of the asymmetric traveling salesman polytope
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• On the Linear Description of the k-cycle Polytope
• The prize collecting traveling salesman problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The Circuit Polytope: Facets
• The Plant Location Problem: New Models and Research Prospects
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• On cycle cones and polyhedra
• Facets of the \(p\)-cycle polytope
• A branch and cut approach to the cardinality constrained circuit problem.

This page was built for publication: Facets of the \(p\)-cycle polytope