W pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1016/j.tcs.2011.06.017
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2011
Źródło danych: MOSTWiedzy.pl - publikacja "Connected searching of weighted trees" link otwiera się w nowej karcie
