Exact and approximate algorithms for movement problems on (special classes of) graphs
From MaRDI portal
Publication:338392
DOI10.1016/j.tcs.2016.09.007zbMath1353.68255MaRDI 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
90C35: Programming involving graphs or networks
68W05: Nonnumerical algorithms
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
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)