zbMATH — the first resource for mathematics

The Euclidean traveling salesman problem is NP-complete. (English) Zbl 0386.90057

90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
05C30 Enumeration in graph theory
94C15 Applications of graph theory to circuits and networks
05B40 Combinatorial aspects of packing and covering
Full Text: DOI
[1] Garey, M.R.; Graham, R.I.; Johnson, D.S., Some NP-complete geometric problems, Proc. 8th ACM symp. theory comput., 10-29, (1976) · Zbl 0377.68036
[2] Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified NP-complete problems, Proc. 6th STOC, 47-63, (1974)
[3] Held, M.; Karp, R.M., A dynamic programming approach to sequencing problems, J. SIAM, 10, 196-209, (1962) · Zbl 0106.14103
[4] D.S. Johnson, private communication (October 1975).
[5] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[6] Lin, S.; Kernighan, B.W., An effective heuristic algorithm for the traveling salesman problem, Operationas res., 21, 498-516, (1973) · Zbl 0256.90038
[7] C.H. Papadimitriou and K. Steiglitz, On the complexity of local search for the traveling salesman problem, SIAM J. Comput. to appear. · Zbl 0381.68043
[8] Sahni, S.; Gonzales, T., P-complete problems and approximate solutions, J. ACM, 23, 554-564, (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.