Faces of diameter two on the Hamilton cycle polytope

Faces of diameter two on the Hamilton cycle polytope

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.