The complexity of zero-visibility cops and robber

DOI10.1016/J.TCS.2015.03.022MaRDI QIDQ897941zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Danny Dyer, Ryan M. Tifenbach, 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

treepursuit evasiongraph searchingcops and robber

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Characterizations of \(k\)-copwin graphs
• Cops and robbers is EXPTIME-complete
• Interval graphs and searching
• Mixed Search Number and Linear-Width of Interval and Split Graphs
• Monotonicity in graph searching
• On the pathwidth of chordal graphs
• Searching Cycle-Disjoint Graphs
• Searching and pebbling
• The complexity of searching a graph
• The game of cops and robbers on graphs
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width
• Vertex-to-vertex pursuit in a graph
• Zero-visibility cops and robber game on a graph

Cited in

(15)

• Cops, a fast robber and defensive domination on interval graphs
• Computing the one-visibility copnumber of trees
• 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 complexity of zero-visibility cops and robber
• One-visibility cops and robber on trees: optimal cop-win strategies
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• One-visibility cops and robber on trees
• The zero-visibility cops and robber game on graph products
• Zero-visibility cops and robber and the pathwidth of a graph
• A note on hyperopic cops and robber
• Zero-visibility cops and robber game on a graph
• Non-adaptive and adaptive two-sided search with fast objects
• The one-visibility localization game

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)