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

DOI10.1016/J.TCS.2016.09.007MaRDI QIDQ338392zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

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

approximation algorithmsgraph algorithmsmotion planning problemsshortest path movement

Mathematics Subject Classification ID

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

Recommendations

• Exact and approximate algorithms for movement problems on (special classes of) graphs
• \(O(1)\)-approximations for maximum movement problems
• Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems
• Exact algorithms for difficult graph problems
• Algorithms for solving problems on graphs of bounded pathwidth
• Approximation algorithms for graph approximation problems
• scientific article; zbMATH DE number 3929052

Cites work

• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Annealed replication: A new heuristic for the maximum clique problem
• Local-search based approximation algorithms for mobile facility location problems (extended abstract)
• Minimizing Movement: Fixed-Parameter Tractability
• Minimizing movement
• Minimizing movement in mobile facility location problems
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Polygon-constrained motion planning problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• \(O(1)\)-approximations for maximum movement problems

Cited in

(14)

• Minimizing Movement: Fixed-Parameter Tractability
• Minimizing movement
• Motion planning in Cartesian product graphs
• Reconfigurations in Graphs and Grids
• Graphs, Maneuvers and Turnpikes
• Euclidean movement minimization
• Exact and approximate algorithms for movement problems on (special classes of) graphs
• New approximation algorithms for the heterogeneous weighted delivery problem
• New approximation algorithms for the heterogeneous weighted delivery problem
• \(O(1)\)-approximations for maximum movement problems
• Minimizing movement: fixed-parameter tractability
• Polygon-constrained motion planning problems
• On the fastest moving off from a vertex in directed regular graphs
• Minimizing movement

This page was built for publication: Exact and approximate algorithms for movement problems on (special classes of) graphs

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