A Theorem on Symmetric Traveling Salesman Problems

Helmut Steckhan
Additional contact information
Helmut Steckhan: University of Heidelberg, Heidelberg, Germany

Operations Research, 1970, vol. 18, issue 6, 1163-1167

Abstract: This paper shows how to eliminate arcs from a complete directed finite graph so that a maximum number of hamiltonian circuits is destroyed while their reverses are preserved. For all complete directed finite graphs containing more than two nodes, this effect is achieved by eliminating just three arcs that form an elementary circuit. This result can be used in calculating branch-and-bound solutions for symmetric traveling salesman problems.

Date: 1970
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.18.6.1163 (application/pdf)

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:inm:oropre:v:18:y:1970:i:6:p:1163-1167

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().