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

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

Recommendations

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

Cited in

(16)

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

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)