Pursuing a fast robber on a graph
From MaRDI portal
Publication:2268876
DOI10.1016/J.TCS.2009.12.010zbMATH Open1192.91027OpenAlexW2065848091WikidataQ60488639 ScholiaQ60488639MaRDI QIDQ2268876FDOQ2268876
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
Recommendations
complexitycops and robbersparameterized complexityplanar graphcliquewidthpursuit-evasion game on graphs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)
Cites Work
- Graph searching and a min-max theorem for tree-width
- Graph Classes: A Survey
- Cops and robbers in graphs with large girth and Cayley graphs
- A partial k-arboretum of graphs with bounded treewidth
- On the cop number of a graph
- Which problems have strongly exponential complexity?
- On a game of policemen and robber
- Vertex-to-vertex pursuit in a graph
- A note on \(k\)-cop, \(l\)-robber games on 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?)
- Title not available (Why is that?)
- Asteroidal Triple-Free Graphs
- On the pathwidth of chordal graphs
- Searching and sweeping graphs: a brief survey
- Title not available (Why is that?)
- Some results about pursuit games on metric spaces obtained through graph theory techniques
- The complexity of pursuit on a graph
- Graph searching on some subclasses of chordal graphs
- On miniaturized problems in parameterized complexity theory
- On a pursuit game on Cayley graphs
- 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 played on graphs for which a minor is excluded
- Title not available (Why is that?)
- A better bound for the cop number of general graphs
- Note on a pursuit game played on graphs
- On a pursuit game on Cayley digraphs
- Some combinatorial game problems require Ω( n k ) time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast Robber in Planar Graphs
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
- Connected Search for a Lazy Robber
- Guard games on graphs: keep the intruder out!
- Title not available (Why is that?)
- 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
- A cops and robber game and the meeting time of synchronous directed walks
- On the computational complexity of a game of cops and robbers
- Fine-grained Lower Bounds on Cops and Robbers
- 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
- Cops and robbers is EXPTIME-complete
- Catching a fast robber on the grid
- Cops and robbers on 1-planar graphs
- Variations of cops and robbers game on grids
- Cops and robber on butterflies and solid grids
- Zombie number of the Cartesian product of graphs
- Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
- Cops and robber game without recharging
- 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
- Spy game: FPT-algorithm, hardness and graph products
- Spy game: FPT-algorithm and results on graph products
- Linguistic geometry approach for solving the cops and robber problem in grid environments
- 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
- Lower bounds for the cop number when the robber is fast
- Cops and robber on subclasses of \(P_5\)-free graphs
- 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)
