Repozytorium publikacji - Politechnika Gdańska

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

Autorzy

• Robert Kozakiewicz link otwiera się w nowej karcie ,
• dr inż. Robert Lewoń link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie