Cops and Robber with Constraints

DOI10.1137/110837759zbMath1248.05120OpenAlexW2064571607WikidataQ60488471 ScholiaQ60488471MaRDI QIDQ2910936

Paweł Prałat, Fedor V. Fomin, Petr A. Golovach

Publication date: 12 September 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110837759

zbMATH Keywords

pursuit-evasion game on undirected graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Unnamed Item, Spy game: FPT-algorithm, hardness and graph products, Spy game: FPT-algorithm and results on graph products, Spy-game on graphs: complexity and simple topologies, Cops and robbers is EXPTIME-complete, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems