RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2018, Volume 25, Number 1, Pages 5–24 (Mi da887)  

On the skeleton of the polytope of pyramidal tours

V. A. Bondarenko, A. V. Nikolaev

Demidov Yaroslavl State University, 14 Sovetskaya St., 150003 Yaroslavl, Russia

Abstract: We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city $1$, then visits some cities in increasing order of their numbers, reaches city $n$, and returns to city $1$ visiting the remaining cities in decreasing order. The polytope $\mathrm{PYR}(n)$ is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph $K_n$. The skeleton of $\mathrm{PYR}(n)$ is the graph whose vertex set is the vertex set of $\mathrm{PYR}(n)$ and the edge set is the set of geometric edges or one-dimensional faces of $\mathrm{PYR}(n)$. We describe the necessary and sufficient condition for the adjacency of vertices of the polytope $\mathrm{PYR}(n)$. On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of $\mathrm{PYR}(n)$ equals $2$, and the asymptotically exact estimate of the clique number of the skeleton of $\mathrm{PYR}(n)$ is $\Theta(n^2)$. It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons. Illustr. 4, bibliogr. 23.

Keywords: pyramidal tour, $1$-skeleton, necessary and sufficient condition of adjacency, clique number, graph diameter.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation АААА-А16-116070610022-6


DOI: https://doi.org/10.17377/daio.2018.25.570

Full text: PDF file (349 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:1, 9–18

UDC: 519.16+514.172.45
Received: 03.03.2017

Citation: V. A. Bondarenko, A. V. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, Diskretn. Anal. Issled. Oper., 25:1 (2018), 5–24; J. Appl. Industr. Math., 12:1 (2018), 9–18

Citation in format AMSBIB
\Bibitem{BonNik18}
\by V.~A.~Bondarenko, A.~V.~Nikolaev
\paper On the skeleton of the polytope of pyramidal tours
\jour Diskretn. Anal. Issled. Oper.
\yr 2018
\vol 25
\issue 1
\pages 5--24
\mathnet{http://mi.mathnet.ru/da887}
\crossref{https://doi.org/10.17377/daio.2018.25.570}
\elib{http://elibrary.ru/item.asp?id=32729776}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 1
\pages 9--18
\crossref{https://doi.org/10.1134/S1990478918010027}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85043288006}


Linking options:
  • http://mi.mathnet.ru/eng/da887
  • http://mi.mathnet.ru/eng/da/v25/i1/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:107
    Full text:9
    References:14
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020