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)
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
seen 44 times
Recommended for you
Synchronization helps robots to detect black holes in directed graphs
- K. Kosowski,
- A. Navarra,
- C. Pinotti