FACES OF DIAMETER-2 ON THE HAMILTONIAN CYCLE POLYTOPE

G SIERKSMA; RH TEUNTER; GA TIJSSEN

FACES OF DIAMETER-2 ON THE HAMILTONIAN CYCLE POLYTOPE

G SIERKSMA, RH TEUNTER, GA TIJSSEN

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	59-64
Number of pages	6
Journal	Operations Research Letters
Volume	18
Issue number	2
Publication status	Published - Sep-1995

Keywords

TRAVELING SALESMAN PROBLEM
PERFECT 2-MATCHING PROBLEM
DIAMETER
HAMILTONIAN CYCLE

Cite this

@article{f713d6e1ff5143e5bc14558878e834cb,

title = "FACES OF DIAMETER-2 ON THE HAMILTONIAN CYCLE POLYTOPE",

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.",

keywords = "TRAVELING SALESMAN PROBLEM, PERFECT 2-MATCHING PROBLEM, DIAMETER, HAMILTONIAN CYCLE",

author = "G SIERKSMA and RH TEUNTER and GA TIJSSEN",

year = "1995",

month = sep,

language = "English",

volume = "18",

pages = "59--64",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "2",

}

TY - JOUR

T1 - FACES OF DIAMETER-2 ON THE HAMILTONIAN CYCLE POLYTOPE

AU - SIERKSMA, G

AU - TEUNTER, RH

AU - TIJSSEN, GA

PY - 1995/9

Y1 - 1995/9

N2 - 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.

AB - 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.

KW - TRAVELING SALESMAN PROBLEM

KW - PERFECT 2-MATCHING PROBLEM

KW - DIAMETER

KW - HAMILTONIAN CYCLE

M3 - Article

VL - 18

SP - 59

EP - 64

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -