NP-completeness of the Hamming salesman problem
From MaRDI portal
Publication:761246
DOI10.1007/BF01935007zbMath0556.90059MaRDI QIDQ761246
Jyrki Katajainen, Jarmo Ernvall, Martti Penttonen
Publication date: 1985
Published in: BIT (Search for Journal in Brave)
data compressiontraveling salesmanNP-completenessbit strings with Hamming distancesHamming salesman problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Data structures (68P05)
Related Items
Heuristic methods to consecutive block minimization, Hardness and approximation of the asynchronous border minimization problem, Information, possible worlds and the cooptation of scepticism, ON THE HARDNESS OF THE BORDER LENGTH MINIMIZATION PROBLEM ON A RECTANGULAR ARRAY
Cites Work