RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






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


Avtomat. i Telemekh., 2006, Issue 12, Pages 190–204 (Mi at1262)  

Technical Diagnostics

On the solution of the traveling salesman problem once again

P. P. Parkhomenko

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia

Abstract: The procedure is suggested for the construction of Hamiltonian cycles optimized along the length in weighted graphs by the method of the stagewise isolation and lengthening of the linear portions of paths of the minimized length. The procedure makes it possible to process both nonoriented and oriented graphs, i.e., to solve symmetric and nonsymmetric problems of the traveling salesman.
At each stage of the procedure (starting from the first stage), the subgraphs of the initial (original) graph of the problem are processed, the complexity of which decreases in the transitions from stage to stage. The isolation and the lengthening of linear portions of the paths are the simplest operations for the detection of vertices of degree 2 with the possible removal of some edges (arcs) of a subgraph.
These characteristics of the procedure (the stagewise decrease of the complexity of the processable subgraphs and the exceptional simplicity of operations for the isolation and lengthening of the linear portions of paths) permits us to hope for a high effectiveness of the use of the procedure for the solution of the traveling salesman problems of large dimensions.

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

English version:
Automation and Remote Control, 2006, 67:12, 2036–2050

Bibliographic databases:

PACS: 02.10.
Presented by the member of Editorial Board: . . 

Received: 16.03.2006

Citation: P. P. Parkhomenko, “On the solution of the traveling salesman problem once again”, Avtomat. i Telemekh., 2006, no. 12, 190–204; Autom. Remote Control, 67:12 (2006), 2036–2050

Citation in format AMSBIB
\Bibitem{Par06}
\by P.~P.~Parkhomenko
\paper On the solution of the traveling salesman problem once again
\jour Avtomat. i Telemekh.
\yr 2006
\issue 12
\pages 190--204
\mathnet{http://mi.mathnet.ru/at1262}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2283327}
\zmath{https://zbmath.org/?q=an:1194.90110}
\transl
\jour Autom. Remote Control
\yr 2006
\vol 67
\issue 12
\pages 2036--2050
\crossref{https://doi.org/10.1134/S0005117906120150}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33845619444}


Linking options:
  • http://mi.mathnet.ru/eng/at1262
  • http://mi.mathnet.ru/eng/at/y2006/i12/p190

    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
  • Avtomatika i Telemekhanika
    Number of views:
    This page:274
    Full text:123
    References:33
    First page:1

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