In this paper we consider the problem of connected edge searching of weighted trees. It is shown that there exists a polynomial-time algorithm for finding optimal connected search strategy for bounded degree trees with arbitrary weights on the edges and vertices of the tree. The problem is NP-complete for general node-weighted trees (the weight of each edge is 1).
In REF it is also proven that the weighted edge-searching is NP-complete on trees and that there exists a polynomial on tree with bounded degree.
Connected searching of weighted trees
Theoretical Computer Science 412 (2011) 5700-5713
Computer Science Mathematics