Back to Search
Start Over
Approximate search strategies for weighted trees
- Source :
-
Theoretical Computer Science . Dec2012, Vol. 463, p96-113. 18p. - Publication Year :
- 2012
-
Abstract
- Abstract: The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search strategy of a given weighted tree. This in particular yields constant factor approximation algorithms for the (non-connected) classical searching problems and for the weighted pathwidth problem for this class of graphs. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 463
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 83324361
- Full Text :
- https://doi.org/10.1016/j.tcs.2012.07.006