The travelling salesman and the PQ-tree

DOI10.1007/3-540-61310-2_36MaRDI QIDQ4645944zbMATH OpenOpenAlexFDO

Authors Rainer E. Burkard, Vladimir G. Deineko, Gerhard J. Woeginger

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

combinatorial optimizationdynamic programmingEuclidean travelling salesman problempolynomial algorithmPQ-treetravelling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• The travelling salesman and the PQ-tree.
• Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
• Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
• Combinatorial algorithms in concorde
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A method for solving traveling-salesman problems
• A new heuristic for the traveling salesman problem
• Computer Solutions of the Traveling Salesman Problem
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3918121 (Why is no real title available?)
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• On two geometric problems related to the travelling salesman problem
• 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
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(11)

• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
• The travelling salesman and the PQ-tree.
• scientific article; zbMATH DE number 4018804 (Why is no real title available?)
• Combinatorial algorithms in concorde
• scientific article; zbMATH DE number 437539 (Why is no real title available?)
• scientific article; zbMATH DE number 4037195 (Why is no real title available?)
• Data Structures for Traveling Salesmen
• Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
• A class of exponential neighbourhoods for the quadratic travelling salesman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645944)