Article ID: | iaor1997720 |
Country: | Netherlands |
Volume: | 18 |
Issue: | 2 |
Start Page Number: | 59 |
End Page Number: | 64 |
Publication Date: | Oct 1995 |
Journal: | Operations Research Letters |
Authors: | Sierksma Gerard, Tijssen Gert A., Teunter Ruud H. |
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.