Rok 2020

• Tight bounds on global edge and complete alliances in trees

  Publikacja

  • K. Wereszko
  • R. Kozakiewicz
  • R. Lewoń
  • M. Małafiejski

  - Rok 2020

  In the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2017

• Równowaga strategiczna dla zbiorów defensywnych w drzewach

  Publikacja

  • R. Kozakiewicz
  • R. Lewoń
  • M. Małafiejski

  - Rok 2017

  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...

  Pełny tekst do pobrania w serwisie zewnętrznym