RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






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


Trudy Inst. Mat. i Mekh. UrO RAN, 2015, Volume 21, Number 3, Pages 309–317 (Mi timm1222)  

This article is cited in 3 scientific papers (total in 3 papers)

An exact algorithm with linear complexity for a problem of visiting megalopolises

A. G. Chentsovab, M. Yu. Khachaiba, M. Yu. Khachaib

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: A problem of visiting megalopolises with a fixed number of “entrances” and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.

Keywords: traveling salesman problem, $np$-hard problem, dynamic programming, precedence relations.

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

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, 295, suppl. 1, 38–46

Bibliographic databases:

Document Type: Article
UDC: 519.16 + 519.85
Received: 11.05.2015

Citation: A. G. Chentsov, M. Yu. Khachai, M. Yu. Khachai, “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Trudy Inst. Mat. i Mekh. UrO RAN, 21, no. 3, 2015, 309–317; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46

Citation in format AMSBIB
\Bibitem{CheKhaKha15}
\by A.~G.~Chentsov, M.~Yu.~Khachai, M.~Yu.~Khachai
\paper An exact algorithm with linear complexity for a problem of visiting megalopolises
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2015
\vol 21
\issue 3
\pages 309--317
\mathnet{http://mi.mathnet.ru/timm1222}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468113}
\elib{http://elibrary.ru/item.asp?id=24156736}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2016
\vol 295
\issue , suppl. 1
\pages 38--46
\crossref{https://doi.org/10.1134/S0081543816090054}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=WOS:000394441400005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85010430812}


Linking options:
  • http://mi.mathnet.ru/eng/timm1222
  • http://mi.mathnet.ru/eng/timm/v21/i3/p309

    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

    This publication is cited in the following articles:
    1. M. Yu. Khachai, E. D. Neznakhina, “Approximation Schemes for the Generalized Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 97–105  mathnet  crossref  crossref  mathscinet  isi  elib
    2. Khachay M., Neznakhina K., “Polynomial Time Solvable Subclass of the Generalized Traveling Salesman Problem on Grid Clusters”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. VanDerAalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N., N, Springer International Publishing Ag, 2018, 346–355  crossref  mathscinet  isi  scopus
    3. Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55  mathnet  crossref  elib
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:157
    Full text:27
    References:22
    First page:23

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