Abstrakt
W artykule rozważamy problem spójnego przeszukiwania drzew obciążonych. Autorzy w [L. Barriere i inni, Capture of an intruder by mobile agents, SPAA'02 (2002) 200-209] twierdzą, że istnieje wielomianowy algorytm dla problemu obliczania optymalnej strategii przeszukiwania obciążonego drzewa. W niniejszej pracy pokazano, że problem ten jest obliczeniowo trudny nawet dla wierzchołkowo-obciążonych drzew (wagi krawędzi równe 1) oraz podano wielomianowy algorytm konstrukcji strategii przeszukiwania dla drzew o ograniczonym stopniu.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
4
Scopus
Autor (1)
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ły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
LECTURE NOTES IN COMPUTER SCIENCE
nr 6281,
strony 330 - 341,
ISSN: 0302-9743 - Język:
- angielski
- Rok wydania:
- 2010
- Opis bibliograficzny:
- Dereniowski D.: Connected searching of weighted trees// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6281., (2010), s.330-341
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-15155-2_30
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 101 razy