Connected Searching of Weighted Trees

摘要

In this paper we consider the problem of connected edge searching of weighted trees. Authors claim in [L. Barriere at al., Capture of an intruder by mobile agents, SPAA'02 (2002) 200-209] that there exists a polynomial-time algorithm for finding an optimal search strategy. However, due to some flaws in their algorithm, the problem turns out to be open. It is proven in this paper that the considered problem is strongly NP-complete even for node-weighted trees (the weight of each edge is 1). It is also shown that there exists a polynomial-time algorithm for finding an optimal connected search strategy for a given bounded degree tree with arbitrary weights on the edges and on the vertices.