|
|||||
|
|
NP-completeness of the hamming salesman problem |
|
| Authors: | Jarmo Ernvall Jyrki Katajainen Martti Penttonen |
| Institution: | (1) Department of Applied Mathematics, University of Jyväskylä, 40100 Jyväskylä, Finland;(2) Department of Computer Science, University of Turku, 20500 Turku, Finland |
| Abstract: | It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete. |
| Keywords: | NP-completeness traveling salesman problem Hamming distance |
| 本文献已被 SpringerLink 等数据库收录！ | |