This HTML5 document contains 45 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n7http://localhost/temp/predkladatel/
n13http://linked.opendata.cz/resource/domain/vavai/projekt/
n5http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n10http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n18http://bibframe.org/vocab/
n16http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F68407700%3A21240%2F14%3A00214334%21RIV15-MSM-21240___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n9http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n8http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n11http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n19http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F68407700%3A21240%2F14%3A00214334%21RIV15-MSM-21240___
rdf:type
skos:Concept n10:Vysledek
dcterms:description
The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of 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 Robber from entering the guarded region. Fomin et al. (2011) [7] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs. The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of 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 Robber from entering the guarded region. Fomin et al. (2011) [7] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs.
dcterms:title
The guarding game is E-complete The guarding game is E-complete
skos:prefLabel
The guarding game is E-complete The guarding game is E-complete
skos:notation
RIV/68407700:21240/14:00214334!RIV15-MSM-21240___
n3:aktivita
n12:S n12:P n12:I
n3:aktivity
I, P(GBP202/12/G061), P(LL1201), S
n3:cisloPeriodika
0
n3:dodaniDat
n19:2015
n3:domaciTvurceVysledku
n5:3537188
n3:druhVysledku
n11:J
n3:duvernostUdaju
n8:S
n3:entitaPredkladatele
n16:predkladatel
n3:idSjednocenehoVysledku
18672
n3:idVysledku
RIV/68407700:21240/14:00214334
n3:jazykVysledku
n15:eng
n3:klicovaSlova
Cops-and-Robber game; E-completeness; Graph guarding game; Propositional formulas; Pursuit game
n3:klicoveSlovo
n9:Cops-and-Robber%20game n9:Graph%20guarding%20game n9:Propositional%20formulas n9:E-completeness n9:Pursuit%20game
n3:kodStatuVydavatele
GB - Spojené království Velké Británie a Severního Irska
n3:kontrolniKodProRIV
[5773BD76B14A]
n3:nazevZdroje
Theoretical Computer Science
n3:obor
n17:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
2
n3:projekt
n13:GBP202%2F12%2FG061 n13:LL1201
n3:rokUplatneniVysledku
n19:2014
n3:svazekPeriodika
521
n3:tvurceVysledku
Valla, Tomáš Šámal, R.
n3:wos
000331433100008
s:issn
0304-3975
s:numberOfPages
15
n18:doi
10.1016/j.tcs.2013.11.034
n7:organizacniJednotka
21240