Wyszukiwarka
Abstrakt
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.
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 wyróżnionym w JCR
- Opublikowano w:
-
INFORMATION PROCESSING LETTERS
nr 109,
strony 422 - 426,
ISSN: 0020-0190 - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- 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
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 86 razy
Publikacje, które mogą cię zainteresować
An efficient algorithm for finding ideal schedules
- E. G. Coffman Jr.,
- D. Dereniowski,
- W. Kubiak