| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva Pomoč

Naslov:Guarding a subgraph as a tool in pursuit-evasion games
Avtorji:ID Bokal, Drago (Avtor)
ID Jerebic, Janja (Avtor)
Datoteke:URL https://sciendo.com/article/10.7151/dmgt.2244
 
.pdf Guarding_a_Subgraph_as_a_Tool_in_Pu-Bokal-2022.pdf (377,93 KB)
MD5: 11963C3EA41A404EDFA1E31318385747
 
Jezik:Angleški jezik
Vrsta gradiva:Znanstveno delo
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 Novo okno
UDK:519.17
COBISS.SI-ID:8147219 Novo okno
ISSN pri članku:1234-3099
Datum objave v DKUM:17.08.2023
Število ogledov:259
Število prenosov:16
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
Kopiraj citat
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discussiones mathematicae. Graph theory
Skrajšan naslov:Discuss. Math., Graph Theory
Založnik:Technical University Press
ISSN:1234-3099
COBISS.SI-ID:7487065 Novo okno

Licence

Licenca:CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:igra izogibanja zasledovanju, preiskovanje grafov, straženje v grafih, funkcija sence, grafovski retrakti


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici