Weakly cooperative mobile guards in grids.

Adrian Kosowski; Michał Małafiejski; Paweł Żyliński

Weakly cooperative mobile guards in grids.

Abstract

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.

Authors (3)

Adrian Kosowski dr inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Michał Małafiejski dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Paweł Żyliński
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Conference activity
Type:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Language:: English
Publication year:: 2004
Bibliographic description:: Kosowski A., Małafiejski M., Żyliński P.: Weakly cooperative mobile guards in grids.// / : , 2004,
Verified by:: Gdańsk University of Technology