6533b831fe1ef96bd1298cd2
RESEARCH PRODUCT
NP-completeness of the hamming salesman problem
Jyrki KatajainenJarmo ErnvallMartti Penttonensubject
Discrete mathematicsComputer Networks and CommunicationsApplied MathematicsComputer Science::Neural and Evolutionary ComputationHamming distanceComputer Science::Computational ComplexityTravelling salesman problemCombinatoricsHigh Energy Physics::TheoryComputational MathematicsCompleteness (order theory)Computer Science::Data Structures and AlgorithmsNP-completeBottleneck traveling salesman problemHamming codeSoftwareComputer Science::Information TheoryMathematicsdescription
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1985-03-01 | BIT |