Pursuing a fast robber on a graph

DOI10.1016/j.tcs.2009.12.010zbMath1192.91027OpenAlexW2065848091WikidataQ60488639 ScholiaQ60488639MaRDI QIDQ2268876

Nicolas Nisse, Karol Suchan, Fedor V. Fomin, Jan Kratochvíl, 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

complexityplanar graphcops and robbersparameterized complexitycliquewidthpursuit-evasion game on graphs

Mathematics Subject Classification ID

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

Related Items

General cops and robbers games with randomness ⋮ Variations on cops and robbers ⋮ Cops and robber on butterflies and solid grids ⋮ Unnamed Item ⋮ The lion and man game on polyhedral surfaces with obstacles ⋮ Cops and robbers on intersection graphs ⋮ A probabilistic version of the game of zombies and survivors on graphs ⋮ Catching an infinitely fast robber on a grid ⋮ Catching a fast robber on the grid ⋮ Cops and robbers from a distance ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ Cops and invisible robbers: the cost of drunkenness ⋮ The guarding game is E-complete ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Cops and Robber game with a fast robber on expander graphs and random graphs ⋮ Cops and robber on butterflies, grids, and AT-free graphs ⋮ Cops that surround a robber ⋮ Spy game: FPT-algorithm and results on graph products ⋮ To satisfy impatient web surfers is hard ⋮ Cops and robber on subclasses of \(P_5\)-free graphs ⋮ Unnamed Item ⋮ Guard games on graphs: keep the intruder out! ⋮ Zombie number of the Cartesian product of graphs ⋮ The fast robber on interval and chordal graphs ⋮ Escaping an Infinitude of Lions ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Catching a Fast Robber on Interval Graphs ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Spy-game on graphs: complexity and simple topologies ⋮ Cops and robber game without recharging ⋮ Cops and robbers is EXPTIME-complete ⋮ Lower Bounds for the Cop Number when the Robber is Fast ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Variations of cops and robbers game on grids ⋮ Unnamed Item ⋮ Linguistic geometry approach for solving the cops and robber problem in grid environments ⋮ Cops, a fast robber and defensive domination on interval graphs ⋮ Conjectures on Cops and Robbers

Cites Work

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