Maximum vertex occupation time and inert fugitive: recontamination does help [online] - Publikacja - MOST Wiedzy

Wyszukiwarka

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

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.

Słowa kluczowe

Pełna treść

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 13 razy

Publikacje, które mogą cię zainteresować

Meta Tagi