Connected searching of weighted trees

Dariusz Dereniowski

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

Connected searching of weighted trees

Abstract

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.

Citations

3

CrossRef
0

Web of Science
4

Scopus

Author (1)

Dariusz Dereniowski prof. dr hab. inż.

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: LECTURE NOTES IN COMPUTER SCIENCE no. 6281, pages 330 - 341,
ISSN: 0302-9743
Language:: English
Publication year:: 2010
Bibliographic description:: Dereniowski D.: Connected searching of weighted trees// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6281., (2010), s.330-341
DOI:: Digital Object Identifier (open in new tab) 10.1007/978-3-642-15155-2_30
Verified by:: Gdańsk University of Technology