NP-completeness of the Hamming salesman problem

DOI10.1007/BF01935007zbMATH Open0556.90059MaRDI QIDQ761246FDOQ761246

Authors: Jarmo Ernvall, Jyrki Katajainen, Martti Penttonen 

Publication date: 1985

Published in: BIT (Search for Journal in Brave)

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

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)

Cites Work

• The Euclidean traveling salesman problem is NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compact storage schemes for formatted files by spanning trees

Cited In (6)

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

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)