The Travelling Salesman and the PQ-Tree

References

• Booth K. S. , Lueker G. S. Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. System Sci. (1976) 13 335 379 Crossref, Google Scholar
• Burkard R. E. , Van der Veen J. A. A. Universal conditions for algebraic traveling salesman problems to be efficiently solvable. Optimization (1991) 22 787 814 Crossref, Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem (1976) . Technical report, Carnegie Mellon University, Pittsburgh Google Scholar
• Gilmore P. C. , Lawler E. L. , Shmoys D. B. , Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G. , Shmoys D. B. Well-solved special cases. The Travelling Salesman Problem (1985) (Wiley, Chichester) 87 143 Google Scholar
• Held M. , Karp R. M. A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math. (1962) 10 196 210 Crossref, Google Scholar
• Johnson D. S. , Papadimitriou C. H. , Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G. , Shmoys D. B. Performance guarantees for heuristics. The Travelling Salesman Problem (1985) (Wiley, Chichester) 145 180 Google Scholar
• Klyaus P. S. The structure of the optimal solution of certain classes of travelling salesman problems (in Russian). Vestsī Akad. Navuk Belarusī Ser. Fīz. Mat. Navuk (1976) 4 95 98 Google Scholar
• Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G. , Shmoys D. B. The Travelling Salesman Problem (1985) (Wiley, Chichester) Google Scholar
• Papadimitriou C. H. The Euclidean travelling salesman problem is NP-complete. Theoret. Comput. Sci. (1977) 4 237 244 Crossref, Google Scholar
• Papadimitriou C. H. , Steiglitz K. Combinatorial Optimization: Algorithms and Complexity (1982) (Prentice Hall, New Jersey) Google Scholar
• Papadimitriou C. H. , Vazirani U. V. On two geometric problems related to the travelling salesman problem. J. Algorithms (1984) 5 231 246 Crossref, Google Scholar
• Serdyukov A. On some extremal walks in graphs. Upravlyaemye sistemy (1978) 17 76 79 Google Scholar