Trudy Instituta Matematiki i Mekhaniki UrO RAN
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
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 Instituta Matematiki i Mekhaniki UrO RAN, 2015, Volume 21, Number 3, Pages 309–317 (Mi timm1222)  
This article is cited in 19 scientific papers (total in 19 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
Full-text PDF (185 kB) Citations (19)
References:
PDF
HTML
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.
Received: 11.05.2015
English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, Volume 295, Issue 1, Pages 38–46
DOI: https://doi.org/10.1134/S0081543816090054
Bibliographic databases:
Document Type: Article
UDC: 519.16 + 519.85
Language: Russian
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://mathscinet.ams.org/mathscinet-getitem?mr=3468113}
\elib{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=WOS:000394441400005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85010430812}
Linking options:
  • https://www.mathnet.ru/eng/timm1222
  • https://www.mathnet.ru/eng/timm/v21/i3/p309
    • This publication is cited in the following 19 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Statistics & downloads:
    Abstract page:327
    Full-text PDF :67
    References:51
    First page:23
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024