On vertex adjacencies in the polytope of pyramidal tours with step-backs

Abstract

We consider the traveling salesperson problem in a directed graph. The pyramidal tours with step-backs are a special class of Hamiltonian cycles for which the traveling salesperson problem is solved by dynamic programming in polynomial time. The polytope of pyramidal tours with step-backs $PSB(n)$ is defined as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The skeleton of $PSB(n)$ is the graph whose vertex set is the vertex set of $PSB(n)$ and the edge set is the set of geometric edges or one-dimensional faces of $PSB(n)$. The main result of the paper is a necessary and sufficient condition for vertex adjacencies in the skeleton of the polytope $PSB(n)$ that can be verified in polynomial time.

arXiv commentin English

References in corpus (4)

• Vertex adjacencies in the set covering polyhedron
• On the skeleton of the pyramidal tours polytope
• 1-skeletons of the spanning tree problems with additional constraints
• Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems

Cited by in corpus (4)

• An iterative ILP approach for constructing a Hamiltonian decomposition of a regular multigraph
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• Backtracking algorithms for constructing the Hamiltonian decomposition of a 4-regular multigraph
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search