The complexity of zero-visibility cops and robber
DOI10.1016/J.TCS.2015.03.022zbMATH Open1332.68070OpenAlexW1967439097MaRDI QIDQ897941FDOQ897941
Danny Dyer, Ryan M. Tifenbach, Dariusz Dereniowski, Boting Yang
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.022
Recommendations
- The complexity of zero-visibility cops and robber
- Zero-visibility cops and robber game on a graph
- One-visibility cops and robber on trees: optimal cop-win strategies
- Zero-visibility cops and robber and the pathwidth of a graph
- Complexity of the cop and robber guarding game
- A simple method for proving lower bounds in the zero-visibility cops and robber game
- On the computational complexity of a game of cops and robbers
- Conjectures on cops and robbers
- scientific article; zbMATH DE number 6180528
- Fine-grained Lower Bounds on Cops and Robbers
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) 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
- Searching and pebbling
- Vertex-to-vertex pursuit in a graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of searching a graph
- The vertex separation number of a graph equals its path-width
- On the pathwidth of chordal graphs
- The vertex separation and search number of a graph
- Monotonicity in graph searching
- Interval graphs and searching
- Cops and robbers is EXPTIME-complete
- Characterizations of \(k\)-copwin graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Searching Cycle-Disjoint Graphs
- Title not available (Why is that?)
- Zero-Visibility Cops and Robber Game on a Graph
Cited In (13)
- Cops, a fast robber and defensive domination on interval graphs
- The zero-visibility cops and robber game on graph products
- Searching for an intruder on graphs and their subdivisions
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Searching by heterogeneous agents
- The one-visibility localization game
- Computing the one-visibility copnumber of trees
- Limited visibility cops and robber
- A note on hyperopic cops and robber
- Non-adaptive and adaptive two-sided search with fast objects
- One-visibility cops and robber on trees: optimal cop-win strategies
- A simple method for proving lower bounds in the zero-visibility cops and robber game
- One-visibility cops and robber on trees
This page was built for publication: The complexity of zero-visibility cops and robber
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897941)
