Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 202-205 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 105 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2008 Feb 29 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications