|
Discrete mathematics and mathematical cybernetics
On 1-skeleton of the polytope of pyramidal tours with step-backs
A. V. Nikolaev P.G. Demidov Yaroslavl State University, 14, Sovetskaya str., Yaroslavl, 150003, Russia
Abstract:
Pyramidal tours with step-backs are Hamiltonian tours of a special kind: the salesperson starts in city 1, then visits some cities in ascending order, reaches city n, and returns to city 1 visiting the remaining cities in descending order. However, in the ascending and descending direction, the order of neighboring cities can be inverted (a step-back). It is known that on pyramidal tours with step-backs the traveling salesperson problem can be solved by dynamic programming in polynomial time. We define the polytope of pyramidal tours with step-backs PSB(n) as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The 1-skeleton of PSB(n) is the graph whose vertex set is the vertex set of the polytope, and the edge set is the set of geometric edges or one-dimensional faces of the polytope. We present a linear-time algorithm to verify vertex adjacency in the 1-skeleton of the polytope PSB(n) and estimate the diameter and the clique number of the 1-skeleton: the diameter is bounded above by 4 and the clique number grows quadratically in the parameter n.
Keywords:
pyramidal tour with step-backs, 1-skeleton, vertex adjacency, graph diameter, clique number, pyramidal encoding.
Received April 23, 2022, published September 6, 2022
Citation:
A. V. Nikolaev, “On 1-skeleton of the polytope of pyramidal tours with step-backs”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 674–687
Linking options:
https://www.mathnet.ru/eng/semr1530 https://www.mathnet.ru/eng/semr/v19/i2/p674
|
|