Guard games on graphs: keep the intruder out!
DOI10.1016/J.TCS.2011.08.024zbMATH Open1227.68031DBLPjournals/tcs/FominGL11OpenAlexW2336962990WikidataQ60488566 ScholiaQ60488566MaRDI QIDQ650877FDOQ650877
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On the cop number of a graph
- Vertex-to-vertex pursuit in a graph
- A note on \(k\)-cop, \(l\)-robber games on graphs
- Easy problems for tree-decomposable graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A game of cops and robbers
- An annotated bibliography on guaranteed graph searching
- Title not available (Why is that?)
- `` Strong NP-Completeness Results
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Diameter and treewidth in minor-closed graph families
- Title not available (Why is that?)
- Title not available (Why is that?)
- Eternally secure sets, independence sets and cliques
- Pursuing a fast robber on a graph
- Local tree-width, excluded minors, and approximation algorithms
- Title not available (Why is that?)
- Capacitated Domination and Covering: A Parameterized Perspective
- Title not available (Why is that?)
- Tight bounds for eternal dominating sets in graphs
- Guard Games on Graphs: Keep the Intruder Out!
- The Guarding Problem – Complexity and Approximation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of pursuit on a graph
- Title not available (Why is that?)
- A refined search tree technique for dominating set on planar graphs
- Coverage for robotics -- a survey of recent results
- Multi-robot area patrol under frequency constraints
- 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
- Note on a pursuit game played on graphs
- Cop-Robber Guarding Game with Cycle Robber Region
Cited In (4)
This page was built for publication: Guard games on graphs: keep the intruder out!
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650877)
