Dynamic programming and the graphical traveling salesman problem

DOI10.1145/174147.169803MaRDI QIDQ4285636zbMATH OpenOpenAlexFDO

Authors Armand Nachef, Jean Fonlupt

Publication date 24 March 1994

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/174147.169803

zbMATH Keywords

combinatorial optimizationdynamic programmingtraveling salesman problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 34438
• scientific article; zbMATH DE number 4053381
• scientific article; zbMATH DE number 4191425
• The Travelling Salesman Problem in Bounded Degree Graphs

Cited in

(16)

• The traveling salesman problem in graphs with some excluded minors
• New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization
• Optimally solving the joint order batching and picker routing problem
• Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
• A partitioning column approach for solving LED sorter manipulator path planning problems
• Generalisations of the Gilmore-Gomory traveling salesman problem and the Gilmore-Gomory scheme: a survey
• Dynamic programming on a directed graph
• The Steiner traveling salesman problem with online edge blockages
• scientific article; zbMATH DE number 4191425 (Why is no real title available?)
• The traveling salesman problem on a graph and some related integer polyhedra
• The traveling salesman problem in graphs with 3-edge cutsets
• scientific article; zbMATH DE number 37078 (Why is no real title available?)
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• Upgrading edges in the graphical TSP
• A note on computational aspects of the Steiner traveling salesman problem
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems

This page was built for publication: Dynamic programming and the graphical traveling salesman problem

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