Geodesic
On $1$-skeleton of the polytope of pyramidal tours with step-backs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 674-687

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathrm{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 $\mathrm{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 $\mathrm{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. 
@article{SEMR_2022_19_2_a33,
     author = {A. V. Nikolaev},
     title = {On $1$-skeleton of the polytope of pyramidal tours with step-backs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {674--687},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/}
}
TY  - JOUR
AU  - A. V. Nikolaev
TI  - On $1$-skeleton of the polytope of pyramidal tours with step-backs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 674
EP  - 687
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/
LA  - en
ID  - SEMR_2022_19_2_a33
ER  - 
%0 Journal Article
%A A. V. Nikolaev
%T On $1$-skeleton of the polytope of pyramidal tours with step-backs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 674-687
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/
%G en
%F SEMR_2022_19_2_a33
A. V. Nikolaev. On $1$-skeleton of the polytope of pyramidal tours with step-backs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 674-687. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/