Pursuing a fast robber on a graph

DOI10.1016/J.TCS.2009.12.010MaRDI QIDQ2268876zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Jan Kratochvíl, Nicolas Nisse, Karol Suchan, Petr A. Golovach

Publication date 9 March 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.12.010

zbMATH Keywords

complexitycops and robbersparameterized complexityplanar graphcliquewidthpursuit-evasion game on graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Recommendations

• Fast Robber in Planar Graphs
• Cops and robber game without recharging
• On the computational complexity of a game of cops and robbers
• Cops and Robber game without recharging
• A game of cops and robbers

Cites work

• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• scientific article; zbMATH DE number 177438 (Why is no real title available?)
• 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 887776 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 5241699 (Why is no real title available?)
• scientific article; zbMATH DE number 2187680 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A better bound for the cop number of general graphs
• A game of cops and robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• A partial k-arboretum of graphs with bounded treewidth
• A short note about pursuit games played on a graph with a given genus
• An annotated bibliography on guaranteed graph searching
• Asteroidal Triple-Free Graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• Fast Robber in Planar Graphs
• Graph Classes: A Survey
• Graph searching and a min-max theorem for tree-width
• Graph searching on some subclasses of chordal graphs
• Note on a pursuit game played on graphs
• On a game of policemen and robber
• On a pursuit game on Cayley digraphs
• On a pursuit game on Cayley graphs
• On a pursuit game played on graphs for which a minor is excluded
• On miniaturized problems in parameterized complexity theory
• On the cop number of a graph
• On the pathwidth of chordal graphs
• 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
• Some combinatorial game problems require Ω( n ^k ) time
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• The complexity of pursuit on a graph
• Vertex-to-vertex pursuit in a graph
• Which problems have strongly exponential complexity?

Cited in

(47)

• General cops and robbers games with randomness
• Study of a combinatorial game in graphs through linear programming
• Study of a combinatorial game in graphs through linear programming
• Cops, a fast robber and defensive domination on interval graphs
• Guard games on graphs: keep the intruder out!
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• Connected Search for a Lazy Robber
• Fast Robber in Planar Graphs
• Cops and robber on butterflies, grids, and AT-free graphs
• Primal-dual cops and robber
• Spy-game on graphs: complexity and simple topologies
• Escaping an infinitude of lions
• On the computational complexity of a game of cops and robbers
• A cops and robber game and the meeting time of synchronous directed walks
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• The lion and man game on polyhedral surfaces with obstacles
• Cops and invisible robbers: the cost of drunkenness
• Fine-grained Lower Bounds on Cops and Robbers
• Cops and robbers is EXPTIME-complete
• Catching a fast robber on the grid
• Cops and robber on butterflies and solid grids
• Cops and robbers on 1-planar graphs
• Variations of cops and robbers game on grids
• Zombie number of the Cartesian product of graphs
• Cops and robber game without recharging
• Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
• The fast robber on interval and chordal graphs
• A faster algorithm for cops and robbers
• Catching an infinitely fast robber on a grid
• Chasing a fast robber on planar graphs and random graphs
• A probabilistic version of the game of zombies and survivors on graphs
• Variations on cops and robbers
• Linguistic geometry approach for solving the cops and robber problem in grid environments
• Spy game: FPT-algorithm, hardness and graph products
• Spy game: FPT-algorithm and results on graph products
• Cops and robbers from a distance
• Conjectures on cops and robbers
• Connected search for a lazy robber
• Cops and robber with constraints
• Edge degeneracy: algorithmic and structural results
• Cops that surround a robber
• Catching a fast robber on interval graphs
• Cops and robber on subclasses of \(P_5\)-free graphs
• Lower bounds for the cop number when the robber is fast
• Cops and Robber game with a fast robber on expander graphs and random graphs
• To satisfy impatient web surfers is hard
• The guarding game is E-complete

This page was built for publication: Pursuing a fast robber on a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268876)