Back to Search
Start Over
The weight-constrained maximum-density subtree problem and related problems in trees.
- Source :
-
Journal of Supercomputing . Dec2010, Vol. 54 Issue 3, p366-380. 15p. 2 Diagrams, 6 Charts. - Publication Year :
- 2010
-
Abstract
- Given a tree T=( V, E) of n nodes such that each node v is associated with a value-weight pair ( val, w), where value val is a real number and weight w is a non-negative integer, the density of T is defined as $\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}$. A subtree of T is a connected subgraph ( V′, E′) of T, where V′⊆ V and E′⊆ E. Given two integers w and w, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=( V′, E′) satisfying w≤∑ w≤ w. In this paper, we first present an O( w n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S⊂ V, we also present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09208542
- Volume :
- 54
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Journal of Supercomputing
- Publication Type :
- Academic Journal
- Accession number :
- 54887474
- Full Text :
- https://doi.org/10.1007/s11227-009-0328-z