Exact and approximate algorithms for movement problems on (special classes of) graphs

DOI10.1016/j.tcs.2016.09.007zbMath1353.68255OpenAlexW2519873941MaRDI QIDQ338392

Stefano Leucci, Guido Proietti, Davide Bilò, Luciano Gualà

Publication date: 4 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.09.007

zbMATH Keywords

graph algorithmsapproximation algorithmsmotion planning problemsshortest path movement

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

New approximation algorithms for the heterogeneous weighted delivery problem, New approximation algorithms for the heterogeneous weighted delivery problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Annealed replication: A new heuristic for the maximum clique problem
• Polygon-constrained motion planning problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Minimizing movement
• O(1)-Approximations for Maximum Movement Problems
• Minimizing movement in mobile facility location problems
• On the power of unique 2-prover 1-round games
• Minimizing Movement: Fixed-Parameter Tractability
• Local-Search based Approximation Algorithms for Mobile Facility Location Problems: (Extended Abstract)