Connected searching of weighted trees (Q719311): Difference between revisions

Given a simple undirected graph and an invisible fugitive located on an edge, the task is to design a sequence of moves of a team of searchers that results in capturing the fugitive (for a survey see [\textit{B. Alspach}, Matematiche 59, No. 1--2, 5--37 (2004; Zbl 1195.05019)]). The fugitive knows the graph and in each move he can traverse a path of the graph that is free of searchers. A searcher moves along an edge. An edge is clear if it cannot contain the fugitive. A search is connected if after each move of the searchers the subgraph that is clear is connected. These rules are extended also for weighted graphs, i.e. when vertices and edges have weights (positive integers). The goal is to minimize the number of searchers to clear every edge of the graph. In this paper it is proven that the problem is strongly NP-hard even for vertex-weighted trees with one vertex of degree greater than 2 (and all edge weights equal to 1). On the other hand, a polynomial-time algorithm is presented for bounded degree tree (with arbitrary edge weights and vertex weights).