Skip to Content

The Euclidean travelling salesman problem is NP-complete

   Info_icon.svg       BibTeX_logo.svg   
Christos H. Papadimitriou
Theoretical Computer Science 4(3), pages 237–244
1977

The Traveling Salesman Problem is shown to be NP-Complete even if its instances are restricted to be realizable by sets of points on the Euclidean plane.

journal or series
Journal_icon.svg Theoretical Computer Science (TCS)

The Euclidean travelling salesman problem is NP-complete
— status
published
— sort
article in journal
who
— authors
Christos H. Papadimitriou
where & when
— publication date
1977
— journal
Theoretical Computer Science
— volume no.
4
— issue
3
— pages
237–244
URL
URL
— DOI
10.1016/0304-3975(77)90012-3
ISBN & ISSN
— ISSN
0304-3975
APICe
— journal or series
Theoretical Computer Science