The traveling salesman problem on grids with forbidden neighborhoods

DOI10.1007/s10878-017-0119-zzbMath1383.90029OpenAlexW2590847231MaRDI QIDQ1680496

Anja Fischer, Philipp Hungerländer

Publication date: 16 November 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0119-z

zbMATH Keywords

explicit solutionstraveling salesman problemgridconstrained Euclidean traveling salesman problemshortest Hamiltonian path problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38)

Related Items

Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ On-line exploration of rectangular cellular environments with a rectangular hole

Uses Software

• TSPLIB
• Concorde

Cites Work

• An efficient algorithm for the Knight's tour problem
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• The Euclidean traveling salesman problem is NP-complete
• Solution of the knight's Hamiltonian path problem on chessboards
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• Optimal algorithms for constructing knight's tours on arbitrary \(n\times m\) chessboards
• New approximation results for the maximum scatter TSP
• Proof verification and the hardness of approximation problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Which Rectangular Chessboards Have a Knight's Tour?
• On the Maximum Scatter Traveling Salesperson Problem
• Maximum Scatter TSP in Doubling Metrics
• The Maximum Scatter TSP on a Regular Grid
• Hamilton Paths in Grid Graphs
• Solution of a Large-Scale Traveling-Salesman Problem
• Optimal Covering Tours with Turn Costs
• Unnamed Item
• Unnamed Item