Connected searching of weighted trees

Dariusz Dereniowski
Arxiv ID: 1001.4341Last 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.
Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.