Complexity of the cop and robber guarding game
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of the cop and robber guarding game
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
Complexity of the cop and robber guarding game
Popis výsledku anglicky
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
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
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
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Svazek periodika
7056
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
13
Strana od-do
361-373
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—