NP-completeness of the Hamming salesman problem

DOI10.1007/BF01935007zbMath0556.90059MaRDI QIDQ761246

Jyrki Katajainen, Jarmo Ernvall, Martti Penttonen

Publication date: 1985

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

data compressiontraveling salesmanNP-completenessbit strings with Hamming distancesHamming salesman problem

Mathematics Subject Classification ID

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

• The Euclidean traveling salesman problem is NP-complete
• Compact storage schemes for formatted files by spanning trees
• Unnamed Item
• Unnamed Item