Note on Upper Bounds for TSP Domination Number

Authors

  • 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

Keywords:

Traveling salesman problem, domination analysis, complexity, approximation algorithms

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.

Downloads

Published

2006-01-24

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

Issue

Vol. 1 No. 1 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.