Wyszukiwarka
Abstrakt
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.
Cytowania
-
9
CrossRef
-
0
Web of Science
-
1 2
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
nr 37,
strony 59 - 71,
ISSN: 0925-7721 - Język:
- angielski
- Rok wydania:
- 2007
- Opis bibliograficzny:
- Kosowski A., Małafiejski M., Żyliński P.: Cooperative mobile guards in grids// COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS. -Vol. 37., nr. nr 2 (2007), s.59-71
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.comgeo.2006.11.002
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 109 razy