Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сибирские электронные математические известия, 2022, том 19, выпуск 2, страницы 674–687
DOI: https://doi.org/10.33048/semi.2022.19.056
(Mi semr1530)
 

Дискретная математика и математическая кибернетика

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
Список литературы:
Аннотация: 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$.
Ключевые слова: pyramidal tour with step-backs, $1$-skeleton, vertex adjacency, graph diameter, clique number, pyramidal encoding.
Финансовая поддержка Номер гранта
P.G. Demidov Yaroslavl State University VIP-016
The research is supported by the P.G. Demidov Yaroslavl State University Project VIP-016.
Поступила 23 апреля 2022 г., опубликована 6 сентября 2022 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16, 514.172.45
MSC: 52B05, 52B12, 90C57
Язык публикации: английский
Образец цитирования: A. V. Nikolaev, “On $1$-skeleton of the polytope of pyramidal tours with step-backs”, Сиб. электрон. матем. изв., 19:2 (2022), 674–687
Цитирование в формате AMSBIB
\RBibitem{Nik22}
\by A.~V.~Nikolaev
\paper On $1$-skeleton of the polytope of pyramidal tours with step-backs
\jour Сиб. электрон. матем. изв.
\yr 2022
\vol 19
\issue 2
\pages 674--687
\mathnet{http://mi.mathnet.ru/semr1530}
\crossref{https://doi.org/10.33048/semi.2022.19.056}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478156}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1530
  • https://www.mathnet.ru/rus/semr/v19/i2/p674
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024