Complexity of the cop and robber guarding game

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10101028" target="_blank" >RIV/00216208:11320/11:10101028 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-642-25011-8_29" target="_blank" >http://dx.doi.org/10.1007/978-3-642-25011-8_29</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-25011-8_29" target="_blank" >10.1007/978-3-642-25011-8_29</a>

Result language

angličtina

Original language name

Complexity of the cop and robber guarding game

Original language description

The guarding game is a game in which several cops has to guard a region in a (directed or undirected) graph against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, the robber on the remaining vertices (the robber-region). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent the robber from entering the guarded region. The problem is highly nontrivial even for very simple graphs. It is known that when the robber-region is a tree, the problem is NP-complete, and if the robber-region is a directed acyclic graph, the problem becomes PSPACE-complete [Fomin, Golovach, Hall, Mihalák, Vicari, Widmayer: How to Guard a Graph? Algorithmica, DOI: 10.1007/s00453-009-9382-4]. We solve the question asked by Fomin et al. in the previously mentioned p

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2011

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Volume of the periodical

7056

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

13

Pages from-to

361-373

UT code for WoS article

—

EID of the result in the Scopus database

—