| NP-completeness of the Hamming salesman problem | |
| Authors: | Jarmo Ernvall, Jyrki Katajainen, and Martti Penttonen |
| Published in: | BIT 25,1 (1985), 289-292 |
| Full text: |  PDF (380 kB) |
| DOI: | 10.1007/BF01935007 |
| Copyright: | © Springer |
| Abstract: | It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete. |
| BibLATEX: | @article{EKP1985J,
author = {Jarmo Ernvall and Jyrki Katajainen and Martti Penttonen},
title = {{NP}-completeness of the {H}amming salesman problem},
journaltitle = {BIT},
volume = {25},
number = {1},
year = {1985},
pages = {289--292},
}
|