Search
Abstract
W pracy rozważany jest problem defensywnej równowagi strategicznej dla zbiorów defensywnych w drzewach (spójnych grafach acyklicznych), który polega na znalezieniu dwóch rozłącznych globalnych zbiorów defensywnych. Zagadnienie to znajduje zastosowanie w modelo- waniu problemów komunikacyjnych w sieciach. Dla danego grafu G podzbiór jego wierzchołków S jest zbiorem defensywnym, jeśli dla każdego wierzchołka v należącego do S spełniony jest warunek koalicyjny, tzn. w jego domkniętym sąsiedztwie jest co najmniej tyle samo wierzchołków z S co spoza S lub istnieje wierzchołek u sąsiedni do v taki, że w domkniętym sąsiedztwie krawędzi {v, u} jest co najmniej tyle samo wierzchołków z S co spoza S. W pracy pokazana została równoważność między problemami równowagi strategicznej oraz doskonałej równowagi strategicznej dla zbiorów defensywnych w drzewach oraz przedstawiony został wielomianowy algorytm rozwiązujący problem równowagi strategicznej dla zbiorów defensywnych w drzewach
Authors (3)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Title of issue:
- W : Aplikacyjne metody obliczeniowe oraz zarządzanie danymi strony 100 - 109
- Language:
- Polish
- Publication year:
- 2017
- Bibliographic description:
- KOZAKIEWICZ R., Lewoń R., Małafiejski M.: Równowaga strategiczna dla zbiorów defensywnych w drzewach// Aplikacyjne metody obliczeniowe oraz zarządzanie danymi/ ed. Jakub Pizoń, Beata A. Nowak Lublin: Wydawnictwo Naukowe TYGIEL sp. z o.o., 2017, s.100-109
- Verified by:
- Gdańsk University of Technology
seen 122 times
Recommended for you
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 authors