The skeleton of the symmetric Traveling Salesman Polytope

DOI10.1016/0166-218X(93)90169-OzbMath0818.05059MaRDI QIDQ1801669

Gerard Sierksma

Publication date: 23 July 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

diameterHamiltonian cyclescliquescomplete graphskeletoninterchange graphtraveling salesman polytopeHamiltonian tours

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Combinatorial optimization (90C27) Graph theory (05C99) Eulerian and Hamiltonian graphs (05C45)

Related Items

On the Skeleton of the Polytope of Pyramidal Tours ⋮ Interchange graphs and the Hamiltonian cycle polytope ⋮ The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract) ⋮ Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search ⋮ Partial monotonizations of Hamiltonian cycle polytopes: Dimensions and diameters ⋮ Signed orders, choice probabilities, and linear polytopes

Cites Work

• Hamiltonicity in (0-1)-polyhedra
• On the symmetric travelling salesman problem I: Inequalities
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• The adjacency relation on the traveling salesman polytope is NP-Complete
• On the Tours of a Traveling Salesman
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item