Probabilistic Analysis of Edge Elimination for Euclidean TSP

References

• [1] Englert M, Röglin H, Vöcking B (2014) Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica 68(1):190–264.Crossref, Google Scholar
• [2] Garey MR, Graham RL, Johnson DS (1976) Some NP-complete geometric problems. Proc. Eighth Annu. ACM Sympos. Theory Comput. STOC’76 (Association for Computing Machinery, New York), 10–22.Google Scholar
• [3] Hougardy S, Schroeder RT (2014) Edge elimination in TSP instances. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 8747 (Springer, Cham, Switzerland), 275–286.Crossref, Google Scholar
• [4] Jonker R, Volgenant T (1984) Nonoptimal edges for the symmetric traveling salesman problem. Oper. Res. 32(4):837–846.Link, Google Scholar
• [5] Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity of Computer Computations (Springer, New York), 85–103.Crossref, Google Scholar
• [6] Papadimitriou CH (1977) The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci. 4(3):237–244.Crossref, Google Scholar
• [7] Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar