A LIFO Implicit Enumeration Algorithm for the Asymmetric Traveling Salesman Problem Using a One-Arborescence Relaxation.

Abstract

The author proposes a LIFO implicit enumeration algorithm for the asymmetric traveling salesman problem in which the one-arborescence relaxation of the traveling salesman problem (originally suggested by Held and Karp) is employed as a fathoming device. The efficient Edmonds-Fulkerson algorithm is used to construct minimum-cost arborescences. Computational exerpience with the algorithm is also presented.

Document Details

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

Entities

People

  • Theunis H. C. Smith

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Africa
  • Algorithms
  • Continents
  • Engineering
  • Geographic Regions
  • Industrial Research
  • South Africa

Readers

  • Operations Research