caa a22 4500 445805420 CHVBK 20180608132847.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-009-9382-4 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9382-4 How to Guard a Graph? [Elektronische Daten] [Fedor Fomin, Petr Golovach, Alex Hall, Matúš Mihalák, Elias Vicari, Peter Widmayer] We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) 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). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber's or the cops' regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber's region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree (or even in a star), then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a directed acyclic graph, the problem becomes PSPACE-complete. Springer Science+Business Media, LLC, 2010 Game of Cops and Robbers nationallicence Guarding of vertices nationallicence Winning strategy nationallicence Complexity nationallicence Algorithms nationallicence Approximation nationallicence Fomin Fedor Institute of Informatics, University of Bergen, Bergen, Norway aut Golovach Petr School of Engineering and Computing Sciences, Durham University, Durham, UK aut Hall Alex Google, Zurich, Switzerland aut Mihalák Matúš Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut Vicari Elias Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut Widmayer Peter Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut Algorithmica Springer-Verlag 61/4(2011-12-01), 839-856 0178-4617 61:4<839 2011 61 453 https://doi.org/10.1007/s00453-009-9382-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9382-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fomin Fedor Institute of Informatics, University of Bergen, Bergen, Norway aut NATIONALLICENCE 700 1- Golovach Petr School of Engineering and Computing Sciences, Durham University, Durham, UK aut NATIONALLICENCE 700 1- Hall Alex Google, Zurich, Switzerland aut NATIONALLICENCE 700 1- Mihalák Matúš Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut NATIONALLICENCE 700 1- Vicari Elias Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut NATIONALLICENCE 700 1- Widmayer Peter Institute of Theoretical Computer Science, ETH Zurich, Universitaetstrasse 6, 8092, Zurich, Switzerland aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 839-856 0178-4617 61:4<839 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 445805420 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer