NP-completeness of the Hamming salesman problem

DOI10.1007/BF01935007MaRDI QIDQ761246zbMATH OpenFDO

Authors Jarmo Ernvall, Jyrki Katajainen, Martti Penttonen

Publication date 1985

Published in BIT (Search for Journal in Brave)

zbMATH Keywords

NP-completenessdata compressiontraveling salesmanbit strings with Hamming distancesHamming salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Integer programming (90C10)

Recommendations

• On the traveling salesman problem in binary Hamming spaces
• The NPO-completeness of the longest Hamiltonian cycle problem
• NP-completeness of a combinator optimization problem
• Hamiltonian index is NP-complete
• Algorithms and Computation
• Hamming approximation of NP witnesses
• scientific article; zbMATH DE number 1775419
• Trahtenbrot-Zykov problem and NP-completeness
• Decidability of NP-complete problems
• NP-completeness of the linear complementarity problem

Cites work

• scientific article; zbMATH DE number 3872698 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• Compact storage schemes for formatted files by spanning trees
• The Euclidean traveling salesman problem is NP-complete

Cited in

(6)

• On the hardness of the border length minimization problem on a rectangular array
• Information, possible worlds and the cooptation of scepticism
• The Mersenne Low Hamming Combination Search problem can be reduced to an ILP problem
• Hardness and approximation of the asynchronous border minimization problem
• Heuristic methods to consecutive block minimization
• Hamiltonian index is NP-complete

This page was built for publication: NP-completeness of the Hamming salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761246)