FACES OF DIAMETER-2 ON THE HAMILTONIAN CYCLE POLYTOPE

G SIERKSMA, RH TEUNTER, GA TIJSSEN

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)59-64
    Number of pages6
    JournalOperations Research Letters
    Volume18
    Issue number2
    Publication statusPublished - Sep-1995

    Keywords

    • TRAVELING SALESMAN PROBLEM
    • PERFECT 2-MATCHING PROBLEM
    • DIAMETER
    • HAMILTONIAN CYCLE

    Cite this