Some properties of the skeleton of the pyramidal tours polytope

DOI10.1016/j.endm.2017.06.030zbMath1378.05036arXiv1710.06286OpenAlexW2742229541MaRDI QIDQ1689899

Andrei Nikolaev, Vladimir E. Bondarenko

Publication date: 18 January 2018

Full work available at URL: https://arxiv.org/abs/1710.06286

zbMATH Keywords

pyramidal tourclique numbergraph diameter1-skeletonnecessary and sufficient condition of adjacency

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm ⋮ On the Skeleton of the Polytope of Pyramidal Tours

Cites Work

• Unnamed Item
• Unnamed Item
• Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
• On graphs of the cone decompositions for the min-cut and max-cut problems
• Faces of diameter two on the Hamiltonian cycle polytope
• The adjacency relation on the traveling salesman polytope is NP-Complete
• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

This page was built for publication: Some properties of the skeleton of the pyramidal tours polytope