The complexity of zero-visibility cops and robber
From MaRDI portal
Publication:897941
DOI10.1016/j.tcs.2015.03.022zbMath1332.68070OpenAlexW1967439097MaRDI QIDQ897941
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 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 (11)
Searching for an intruder on graphs and their subdivisions ⋮ A simple method for proving lower bounds in the zero-visibility cops and robber game ⋮ Limited visibility cops and robber ⋮ The one-visibility localization game ⋮ A note on hyperopic cops and robber ⋮ One-visibility cops and robber on trees ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Computing the one-visibility copnumber of trees ⋮ Searching by heterogeneous agents ⋮ One-visibility cops and robber on trees: optimal cop-win strategies ⋮ Cops, a fast robber and defensive domination on interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of \(k\)-copwin graphs
- Interval graphs and searching
- 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
- Searching and pebbling
- Vertex-to-vertex pursuit in a graph
- Cops and robbers is EXPTIME-complete
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Searching Cycle-Disjoint Graphs
- The complexity of searching a graph
- Monotonicity in graph searching
- Zero-Visibility Cops and Robber Game on a Graph
This page was built for publication: The complexity of zero-visibility cops and robber
