In this paper it is shown that faces of the Hamiltonian cycle polytope (also called the symmetric traveling salesman polytope) formed by the edge union of two cycles for which the symmetric difference contains only alternating cycles without common points, have diameter at most two. As a consequence, a logarithmic upper bound for the diameter of the Hamiltonian cycle polytope and the perfect two-matching polytope are derived.
|Number of pages||6|
|Journal||Operations Research Letters|
|Publication status||Published - Sep-1995|
- TRAVELING SALESMAN PROBLEM
- PERFECT 2-MATCHING PROBLEM
- HAMILTONIAN CYCLE