NP-completeness of the Hamming salesman problem
type: Item
instance of: scholarly article
title: NP-completeness of the Hamming salesman problem
zbMATH Open document ID: 0556.90059
DOI: 10.1007/BF01935007
author: Jarmo Ernvall
author: Jyrki Katajainen
author: Martti Penttonen
published in: BIT
publication date: 1985-01-01T00:00:00Z
review text: It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 3887437
zbMATH Keywords: Hamming salesman problem
zbMATH Keywords: NP-completeness
zbMATH Keywords: data compression
zbMATH Keywords: traveling salesman
zbMATH Keywords: bit strings with Hamming distances
MaRDI profile type: Publication
cites work: Q3339301
cites work: Compact storage schemes for formatted files by spanning trees
cites work: Q4155835
cites work: The Euclidean traveling salesman problem is NP-complete
Recommended article: On the traveling salesman problem in binary Hamming spaces
Recommended article: The NPO-completeness of the longest Hamiltonian cycle problem
Recommended article: NP-completeness of a combinator optimization problem
Recommended article: Hamiltonian index is NP-complete
Recommended article: Algorithms and Computation
Recommended article: Hamming Approximation of NP Witnesses
Recommended article: Q4542552
Recommended article: Trahtenbrot-Zykov problem and NP-completeness
Recommended article: Decidability of NP-complete problems
Recommended article: NP-completeness of the linear complementarity problem
description: scientific article; zbMATH DE number 3887437