The Bottleneck Traveling Salesman Problem
- 1 July 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (3) , 435-448
- https://doi.org/10.1145/322077.322086
Abstract
The bottleneck traveling salesman problem seeks to minimize the maximum length arc over all Hamlltonlan cycles in a graph A probabdlStlC analysis is presented for random problems It is shown that the optimal ob.lectwe value can be closely approximated by a beta function Finally, effective solution techmques are developed and computational experience is reportedKeywords
This publication has 11 references indexed in Scilit:
- Technical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman ProblemOperations Research, 1973
- Almost all Graphs have a Spanning CycleCanadian Mathematical Bulletin, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Technical Note—An Improved Algorithm for the Bottleneck Assignment ProblemOperations Research, 1971
- The traveling-salesman problem and minimum spanning trees: Part IIMathematical Programming, 1971
- The bottleneck transportation problemNaval Research Logistics Quarterly, 1971
- Pathology of Traveling-Salesman Subtour-Elimination AlgorithmsOperations Research, 1971
- The Traveling-Salesman Problem and Minimum Spanning TreesOperations Research, 1970
- Bottleneck extremaJournal of Combinatorial Theory, 1970
- Flows in NetworksPublished by Walter de Gruyter GmbH ,1963