The travelling salesman and the PQ-tree

DOI10.1007/3-540-61310-2_36zbMath1415.90060OpenAlexW1678991643MaRDI QIDQ4645944

Vladimir G. Deǐneko, Gerhard J. Woeginger, Rainer E. Burkard

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_36

zbMATH Keywords

dynamic programmingcombinatorial optimizationpolynomial algorithmtravelling salesman problemPQ-treeEuclidean travelling salesman problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line sorting of twisted sequences in linear time
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Euclidean traveling salesman problem is NP-complete
• Worst-case analysis of a new heuristic for the travelling salesman problem
• A Dynamic Programming Approach to Sequencing Problems
• On two geometric problems related to the travelling salesman problem
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• A new heuristic for the traveling salesman problem
• A Method for Solving Traveling-Salesman Problems
• Computer Solutions of the Traveling Salesman Problem

This page was built for publication: The travelling salesman and the PQ-tree