New edges not used in shortest tours of travelling salesman problems

New edges not used in shortest tours of travelling salesman problems

0.00 Avg rating0 Votes
Article ID: iaor19992661
Country: Netherlands
Volume: 104
Issue: 1
Start Page Number: 129
End Page Number: 138
Publication Date: Jan 1998
Journal: European Journal of Operational Research
Authors:
Abstract:

For the symmetric travelling salesman problem in an Euclidian plane, a geometrical method for finding edges not used in shortest tours of a complete graph is shown. The edges are obtained as pairs, like edges crossing each other. In special cases, the number of these pairs is six times the number of crossing-pairs. Relations between the method introduced here and the shortest spanning tree are discussed.

Reviews

Required fields are marked *. Your email address will not be published.