Sufficient and Necessary Conditions for an Edge in the Optimal Hamiltonian Cycle Based on Frequency Quadrilaterals

Yong Wang ()
Additional contact information
Yong Wang: North China Electric Power University

Journal of Optimization Theory and Applications, 2019, vol. 181, issue 2, No 16, 683 pages

Abstract: Abstract The symmetric traveling salesman problem is studied according to frequency graphs computed with frequency quadrilaterals. Here, we provide the sufficient and necessary conditions for an optimal Hamiltonian cycle edge based on frequency quadrilaterals. If the probability that an edge has frequency 5 in a frequency quadrilateral is 1, it belongs to the optimal Hamiltonian cycle. For an optimal Hamiltonian cycle edge, the probability that it has frequency 5 in a frequency quadrilateral tends to 1 as the scale of traveling salesman problem is sufficiently large.

Keywords: Traveling salesman problem; Optimal Hamiltonian cycle; Frequency quadrilateral; Sufficient condition; Necessary condition; 65K10; 68R10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-01465-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:181:y:2019:i:2:d:10.1007_s10957-018-01465-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-01465-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().