Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs

DOI10.1007/978-3-319-03578-9_27zbMath1353.68254arXiv1407.0628OpenAlexW2202924637MaRDI QIDQ2868655

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

Publication date: 17 December 2013

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.0628

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• 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
• On Representatives of Subsets

This page was built for publication: Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs