Vol 1 No 1 (2006)
Articles

Note on Upper Bounds for TSP Domination Number

Gregory Gutin
Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK
Angela Koller
Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK
Anders Yeo
Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK
Published January 24, 2006
Keywords
  • Traveling salesman problem,
  • domination analysis,
  • complexity,
  • approximation algorithms
How to Cite
Gutin, G., Koller, A., & Yeo, A. (2006). Note on Upper Bounds for TSP Domination Number. Algorithmic Operations Research, 1(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/97

Abstract

The domination number, domn(A, n), of a heuristic A for the Asymmetric TSP is the maximum integer d = d(n) such that, for every instance I of the Asymmetric TSP on n cities, A produces a tour T which is not worse than at least d tours in I including T itself. Two upper bounds on the domination number are proved.