Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "shadow function" wg kryterium: Temat


Wyświetlanie 1-1 z 1
Tytuł:
Guarding a Subgraph as a Tool in Pursuit-Evasion Games
Autorzy:
Bokal, Drago
Jerebic, Janja
Powiązania:
https://bibliotekanauki.pl/articles/32361747.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
pursuit-evasion game
graph searching
guarding
shadow function
graph retraction
Opis:
Pursuit-evasion games study the number of cops needed to capture the robber in a game played on a graph, in which the cops and the robber move alternatively to neighbouring vertices, and the robber is captured if a cop steps on the vertex the robber is in. A common tool in analyzing this cop number of a graph is a cop moving along a shortest path in a graph, thus preventing the robber to step onto this path. We generalize this approach by introducing a shadow of the robber, the maximal set of vertices from which the cop parries the protected subgraph. In this context, the robber becomes an intruder and the cop becomes the guard. We show that the shadow can be computed in polynomial time, implying polynomial time algorithms for computing both a successful guard as well as a successful intruder, whichever exists. Furthermore, we show that shadow function generalizes the concept of graph retractions. In some cases, this implies a polynomially computable certification of the negative answer to the NP-complete problem of existence of a retraction to a given subgraph.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 123-138
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-1 z 1

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies