Guard games on graphs: keep the intruder out!
From MaRDI portal
Publication:650877
DOI10.1016/j.tcs.2011.08.024zbMath1227.68031OpenAlexW2336962990WikidataQ60488566 ScholiaQ60488566MaRDI QIDQ650877
Daniel Lokshtanov, Fedor V. Fomin, Petr A. Golovach
Publication date: 7 December 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.08.024
Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Positional games (pursuit and evasion, etc.) (91A24)
Related Items (4)
The guarding game is E-complete ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Guarding a subgraph as a tool in pursuit-evasion games
Cites Work
- The complexity of pursuit on a graph
- Multi-robot area patrol under frequency constraints
- A game of cops and robbers
- Note on a pursuit game played on graphs
- An annotated bibliography on guaranteed graph searching
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- On a pursuit game played on graphs for which a minor is excluded
- On the cop number of a graph
- Diameter and treewidth in minor-closed graph families
- Vertex-to-vertex pursuit in a graph
- Pursuing a fast robber on a graph
- Coverage for robotics -- a survey of recent results
- Eternally secure sets, independence sets and cliques
- Tight bounds for eternal dominating sets in graphs
- A note on \(k\)-cop, \(l\)-robber games on graphs
- Local tree-width, excluded minors, and approximation algorithms
- A refined search tree technique for dominating set on planar graphs
- Easy problems for tree-decomposable graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Capacitated Domination and Covering: A Parameterized Perspective
- Guard Games on Graphs: Keep the Intruder Out!
- The Guarding Problem – Complexity and Approximation
- `` Strong NP-Completeness Results
- Approximation algorithms for NP-complete problems on planar graphs
- Cop-Robber Guarding Game with Cycle Robber Region
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Guard games on graphs: keep the intruder out!
