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)

Full work available at URL https://doi.org/10.1007/BF01935007

zbMATH Keywords

bit strings with Hamming distancesdata compressionHamming salesman problemNP-completenesstraveling salesman

Mathematics Subject Classification ID

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

Review text

It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.

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

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

Cited in

(6)

• Hardness and approximation of the asynchronous border minimization problem
• The Mersenne Low Hamming Combination Search problem can be reduced to an ILP problem
• Heuristic methods to consecutive block minimization
• On the hardness of the border length minimization problem on a rectangular array
• Information, possible worlds and the cooptation of scepticism
• 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)