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 programmingpolynomial algorithmtravelling salesman problemPQ-treeEuclidean travelling salesman problem

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(10)

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

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)