## Abstract

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _{v},w _{v} ), where value val _{v} is a real number and weight w _{v} is a non-negative integer, the density of T is defined as Σv∈V Valu/Σv∈Vwv. A subtree of T is a connected subgraph (V′,E′) of T, where V′V and E′E. Given two integers w _{min∈} and w _{max}, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _{min}Σ_{v V′} w _{v} ≤w _{max}. In this paper, we first present an O(w _{max} n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _{max} ^{2} 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 _{max} ^{2} n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.

Original language | English |
---|---|

Pages (from-to) | 366-380 |

Number of pages | 15 |

Journal | Journal of Supercomputing |

Volume | 54 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2010 Dec |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Information Systems
- Hardware and Architecture