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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/978-3-642-15155-2_30
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język
- angielski
- Rok wydania
- 2010
Źródło danych: MOSTWiedzy.pl - publikacja "Connected searching of weighted trees" link otwiera się w nowej karcie
