The complexity of zero-visibility cops and robber

DOI10.1016/j.tcs.2015.03.022zbMath1332.68070MaRDI 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

zbMATH Keywords

tree; pursuit evasion; graph searching; cops and robber

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

91A43: Games involving graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91A24: Positional games (pursuit and evasion, etc.)

Related Items

Searching by heterogeneous agents, The one-visibility localization game, A note on hyperopic cops and robber, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Computing the one-visibility copnumber of trees, One-visibility cops and robber on trees: optimal cop-win strategies, 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, One-visibility cops and robber on trees, 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