The travelling salesman and the PQ-tree

DOI10.1007/3-540-61310-2_36zbMATH Open1415.90060OpenAlexW1678991643MaRDI QIDQ4645944FDOQ4645944

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

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.

zbMATH Keywords

combinatorial optimizationdynamic programmingpolynomial algorithmtravelling salesman problemPQ-treeEuclidean travelling salesman problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Dynamic Programming Approach to Sequencing Problems
• A method for solving traveling-salesman problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Title not available (Why is that?)
• The Euclidean traveling salesman problem is NP-complete
• Worst-case analysis of a new heuristic for the travelling salesman problem
• Title not available (Why is that?)
• 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
• Computer Solutions of the Traveling Salesman Problem
• On two geometric problems related to the travelling salesman problem
• A new heuristic for the traveling salesman problem
• Title not available (Why is that?)
• On-line sorting of twisted sequences in linear time
• Title not available (Why is that?)

Cited In (10)

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

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)