Connected searching of weighted trees
Dariusz Dereniowski
Arxiv ID: 1001.4341•Last updated: 3/5/2021
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).
PaperStudio AI Chat
I'm your research assistant! Ask me anything about this paper.