Praca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla przypadku krat bez dziur oraz oszacowania liczby potrzebnych straży dla krat z niewielką liczbą dziur.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1016/j.comgeo.2006.11.002
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie z listy filadelfijskiej
- Język
- angielski
- Rok wydania
- 2007
Źródło danych: MOSTWiedzy.pl - publikacja "Cooperative mobile guards in grids" link otwiera się w nowej karcie
