20.500.12556/DKUM-85071 Guarding a subgraph as a tool in pursuit-evasion games Pursuit-evasion games study the number of cops needed to capture therobber in a game played on a graph, in which the cops and the robber movealternatively to neighbouring vertices, and the robber is captured if a copsteps on the vertex the robber is in. A common tool in analyzing this copnumber of a graph is a cop moving along a shortest path in a graph, thuspreventing the robber to step onto this path. We generalize this approach byintroducing a shadow of the robber, the maximal set of vertices from whichthe cop parries the protected subgraph. In this context, the robber becomesan intruder and the cop becomes the guard. We show that the shadow canbe computed in polynomial time, implying polynomial time algorithms forcomputing both a successful guard as well as a successful intruder, whicheverexists. Furthermore, we show that shadow function generalizes the conceptof graph retractions. In some cases, this implies a polynomially computablecertification of the negative answer to the NP-complete problem of existenceof a retraction to a given subgraph. pursuit-evasion game graph searching guarding shadow function graph retraction igra izogibanja zasledovanju preiskovanje grafov straženje v grafih funkcija sence grafovski retrakti true true true Angleški jezik Slovenski jezik Članek v reviji 2023-08-17 14:50:06 2023-08-17 14:50:06 2024-02-29 14:13:59 0000-00-00 00:00:00 2021 0 0 str. 123-138 no. 1 Vol. 42 2022 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2022-01-01 519.17 8147219 1234-3099 https://sciendo.com/article/10.7151/dmgt.2244 0 98e39988-3cfc-11ee-af21-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=169675 Guarding_a_Subgraph_as_a_Tool_in_Pu-Bokal-2022.pdf Guarding_a_Subgraph_as_a_Tool_in_Pu-Bokal-2022.pdf 1 11963C3EA41A404EDFA1E31318385747 67f7282ebccaf0ccfec9136db3224a4f073a2faeab03d762c3be364734973d06 56a934e2-3cfd-11ee-af21-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=169677 Fakulteta za naravoslovje in matematiko Fakulteta za organizacijske vede 0 0 0