Guard games on graphs: keep the intruder out!
DOI10.1016/J.TCS.2011.08.024zbMATH Open1227.68031DBLPjournals/tcs/FominGL11OpenAlexW2336962990WikidataQ60488566 ScholiaQ60488566MaRDI QIDQ650877FDOQ650877
Authors: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov 
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
- Searching and sweeping graphs: a brief survey
- 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
- Eternal security in graphs of fixed independence number
- Maximum-demand graphs for eternal security
- Complexity of eternal security
- The complexity of pursuit on a graph
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- 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 (7)
- Guard games on graphs: keep the intruder out!
- How to guard a graph against tree moves
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Spy-game on graphs
- Guarding a subgraph as a tool in pursuit-evasion games
- The guarding game is E-complete
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)
