Maximum vertex occupation time and inert fugitive: recontamination does help [online]

Dariusz Dereniowski

Maximum vertex occupation time and inert fugitive: recontamination does help [online]

Abstract

Rozważamy problem przeszukania danego grafu prostego G w celu przechwycenia niewidocznego i leniwego uciekiniera. Parametrem optymalizacyjnym, który minimalizujemy jest maksymalny czas (liczba tur strategii przeszukiwania), podczas których wierzchołek może być strzeżony (okupowany przez strażnika). Strategia monotoniczna to taka, która nie dopuszcza sytuacji, w której uciekinier dociera do wierzchołka, który wcześniej został oczyszczony. Praca pokazuje fakt, że optymalne rozwiązanie powyższego problemu nie musi w ogólności być strategią monotoniczną. Co więcej, podana została konstrukcja rodziny grafów, dla których maksymalny czas okupacji najlepszej monotonicznej strategii wyszukiwania jest dowolnie większy od tego parametru dla optymalnej strategii.

Author (1)

Dariusz Dereniowski prof. dr hab. inż.

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

TEORIA GRAFÓW

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: INFORMATION PROCESSING LETTERS no. 109, pages 422 - 426,
ISSN: 0020-0190
Language:: English
Publication year:: 2009
Bibliographic description:: Dereniowski D.: Maximum vertex occupation time and inert fugitive: recontamination does help [online]// INFORMATION PROCESSING LETTERS. -Vol. 109, nr. iss. 9 April (2009), s.422-426
Verified by:: Gdańsk University of Technology