Repozytorium publikacji - Politechnika Gdańska

Problem straży w kratach stanowi przypadek problemu minimalnego pokrycia spójnego podzbioru płaszczyzny przez pewne szczególne podzbiory. W modelu tym przyjmuje się, że strażnik porusza się wzdłuż odcinka kraty i widzi wszystkie przecinające się z nim (prostopadłe) odcinki. W rozważanym modelu współpracy zakłada się, że każdy strażnik musi być widziany przez przynajmniej jednego innego strażnika. W pracy pokazano dowód NP-zupełności problemu decyzyjnego, rozważono przypadki krat dla których istnieje jego rozwiązanie wielomianowe i podano oszacowania górne i dolne na wymaganą liczbę strażników w pewnych szczególnych klasach krat.

Autorzy

• dr inż. Adrian Kosowski link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie ,
• Paweł Żyliński