Connected searching of weighted trees

Dariusz Dereniowski

doi:10.1007/978-3-642-15155-2_30

Connected searching of weighted trees

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)

Dariusz Dereniowski prof. dr hab. inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

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