Let T = (V, E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv, wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P = 〈 v1, v2, ..., vk 〉 is defined as ∑i = 1k vali / ∑i = 1k wi. The weight of P, denoted by w (P), is ∑i = 1k wi. Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O (wmax n L)-time algorithm to find a maximum-density path P in T such that wmin ≤ w (P) ≤ wmax and the length of P is at least L.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications