Article
The Satellite List and New Data Structures for Symmetric Traveling Salesman Problems
CiteSeerX
(2004)
Abstract
The problem of data representation is fundamental to the efficiency of search algorithms for the traveling salesman problem (TSP). The computational effort required to perform such tour operations as traversal and subpath reversal considerably influence algorithm design and performance. We propose new data structures—the satellite list and k-level satellite tree—for representing a TSP tour with a discussion of properties in the framework of general tour operations. Theory suggests that the satellite list data structure is superior in representation to its widely used counterpart, the doubly-linked list, as well as useful in improving and extending the specialized 2-level tree structure for symmetric graph-based optimization problems. The k-level satellite tree representation is shown to be far more efficient than its predecessors.
Keywords
- satellite list,
- symmetric traveling salesman problem,
- new data structure,
- computational effort,
- salesman problem,
- k-level satellite tree representation,
- satellite list data structure,
- specialized 2-level tree structure,
- tour operation,
- data representation,
- general tour operation,
- influence algorithm design,
- subpath reversal,
- new data,
- doubly-linked list,
- k-level satellite tree,
- search algorithm,
- symmetric graph-based optimization problem,
- tsp tour
Disciplines
Publication Date
2004
Citation Information
Colin Osterman, Cesar Rego and Keith Womer. "The Satellite List and New Data Structures for Symmetric Traveling Salesman Problems" CiteSeerX (2004) Available at: http://works.bepress.com/keith-womer/40/