A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem

DOI10.1016/0167-6377(91)90035-NzbMath0741.90088OpenAlexW2075524116MaRDI QIDQ1178723

Donald L. Miller, Daniel Stodolsky, Joseph F. Pekny

Publication date: 26 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90035-n

zbMATH Keywords

assignment problemAsymmetric Traveling Salesman Problemdirected admissible graphdirected Hamiltonian cycle problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05) Discrete location and assignment (90B80) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems
• An algorithm for finding hamilton cycles in random directed graphs
• A parallel shortest augmenting path algorithm for the assignment problem
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem