A Subtour Elimination Algorithm for the Bottleneck Traveling Salesman Problem.

Abstract

In this paper we propose a LIFO implicit enumeration algorithm for the bottleneck traveling salesman problem which uses the bottleneck assignment problem as a relaxation. We also present computational experience on a UNIVAC 1108 with symmetric and asymmetric problems, ranging in size from 30 to 2000 nodes. Our results indicate that for asymmetric problems the time requirement of the proposed algorithm grows slower than the square of the problem size -- i.e. the algorithm is empirically good (in the sense of Edmonds). (Author)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1975
Accession Number
ADA019547

Entities

People

  • Gerald L. Thompson
  • T. H. C. Smith

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Elimination

Fields of Study

  • Computer science

Readers

  • Computational Fluid Dynamics (CFD)
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.