Guard games on graphs: keep the intruder out!

DOI10.1016/J.TCS.2011.08.024MaRDI QIDQ650877zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

complexityapproximationparameterized complexityguard games

Mathematics Subject Classification ID

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)

Recommendations

• Guard games on graphs: keep the intruder out!
• The guarding problem -- complexity and approximation
• How to guard a graph?
• How to Guard a Graph?
• How to guard a graph against tree moves

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2174620 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 2104838 (Why is no real title available?)
• scientific article; zbMATH DE number 2114685 (Why is no real title available?)
• scientific article; zbMATH DE number 910922 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A game of cops and robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• A refined search tree technique for dominating set on planar graphs
• An annotated bibliography on guaranteed graph searching
• Approximation algorithms for NP-complete problems on planar graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Complexity of eternal security
• Cop-Robber Guarding Game with Cycle Robber Region
• Coverage for robotics -- a survey of recent results
• Diameter and treewidth in minor-closed graph families
• Easy problems for tree-decomposable graphs
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Eternal security in graphs of fixed independence number
• Eternally secure sets, independence sets and cliques
• Guard games on graphs: keep the intruder out!
• Local tree-width, excluded minors, and approximation algorithms
• Maximum-demand graphs for eternal security
• Multi-robot area patrol under frequency constraints
• Note on a pursuit game played on graphs
• On a pursuit game played on graphs for which a minor is excluded
• On the cop number of a graph
• Pursuing a fast robber on a graph
• Searching and sweeping graphs: a brief survey
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• The complexity of pursuit on a graph
• The guarding problem -- complexity and approximation
• Tight bounds for eternal dominating sets in graphs
• Vertex-to-vertex pursuit in a graph
• `` Strong NP-Completeness Results

Cited in

(7)

• Guarding a subgraph as a tool in pursuit-evasion games
• 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
• How to guard a graph against tree moves
• Guard games on graphs: keep the intruder out!
• 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)