| Naslov: | Guarding a subgraph as a tool in pursuit-evasion games |
|---|
| Avtorji: | ID Bokal, Drago (Avtor)
ID Jerebic, Janja (Avtor) |
|---|
| Datoteke: |  https://sciendo.com/article/10.7151/dmgt.2244
 Guarding_a_Subgraph_as_a_Tool_in_Pu-Bokal-2022.pdf (377,93 KB)
MD5: 11963C3EA41A404EDFA1E31318385747
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
FOV - Fakulteta za organizacijske vede
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | pursuit-evasion game, graph searching, guarding, shadow function, graph retraction |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2022 |
|---|
| Leto izida: | 2021 |
|---|
| Št. strani: | str. 123-138 |
|---|
| Številčenje: | Vol. 42, no. 1 |
|---|
| PID: | 20.500.12556/DKUM-85071  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 8147219 |
|---|
| ISSN pri članku: | 1234-3099 |
|---|
| Datum objave v DKUM: | 17.08.2023 |
|---|
| Število ogledov: | 557 |
|---|
| Število prenosov: | 68 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
