Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Język:
- angielski
- Rok wydania:
- 2004
- Opis bibliograficzny:
- Kosowski A., Małafiejski M., Żyliński P.: Weakly cooperative mobile guards in grids.// / : , 2004,
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 27 razy
Publikacje, które mogą cię zainteresować
Synchronization helps robots to detect black holes in directed graphs
- K. Kosowski,
- A. Navarra,
- C. Pinotti
2009