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.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.comgeo.2006.11.002
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie z listy filadelfijskiej
- Language
- angielski
- Publication year
- 2007
Source: MOSTWiedzy.pl - publication "Cooperative mobile guards in grids" link open in new tab
