Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
15.10.2025 Tomasz Krawczyk PW
Problem Defensywnej Dominacji w klasie grafów przedziałowych
\(\quad\)W problemie Defensywnej Dominacji dla danego grafu G oraz liczb naturalnych l i k należy rozstrzygnąć, czy na wierzchołkach grafu G można rozmieścić l obrońców w taki sposób, aby chronili oni przed atakiem każdy podzbiór A wierzchołków o rozmiarze co najwyżej k (tzn. każdemu wierzchołkowi z atakowanego zbioru A można przypisać prywatnego obrońcę znajdującego się w tym wierzchołku lub w jego sąsiedztwie). Wiadomo, że problem Defensywnej Dominacji jest \(\Sigma_2^P\)-zupełny. Niestety, nie jest znany jego status złożonościowy w prostych klasach grafów, takich jak grafy przedziałowe czy grafy planarne. W swoim referacie przedstawię prosty algorytm zachłanny rozwiązujący problem Defensywnej Dominacji w klasie grafów przedziałowych w przypadku, gdy w każdym wierzchołku grafu można umieścić dowolną liczbę obrońców. Pokażę również, jaki związek zachodzi między klasycznym problemem Defensywnej Dominacji (co najwyżej jeden obrońca na wierzchołek) a problemem plecakowym.
Zespół prowadzący