Cooperative mobile guards in grids

Adrian Kosowski; Michał Małafiejski; Paweł Żyliński

doi:10.1016/j.comgeo.2006.11.002

Cooperative mobile guards in grids

Abstract

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.

Citations

9

CrossRef
0

Web of Science
1 2

Scopus

Authors (3)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie z listy filadelfijskiej
Published in:: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS no. 37, pages 59 - 71,
ISSN: 0925-7721
Language:: English
Publication year:: 2007
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.1016/j.comgeo.2006.11.002
Verified by:: Gdańsk University of Technology