Maximum vertex occupation time and inert fugitive: recontamination does help [online] - Publication - Bridge of Knowledge

Search

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.

Cite as

Full text

full text is not available in portal

Keywords

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

seen 86 times

Recommended for you

Meta Tags