TY - GEN

T1 - Finding a weight-constrained maximum-density subtree in a tree

AU - Hsieh, Sun-Yuan

AU - Chou, Ting Yu

PY - 2005/12/1

Y1 - 2005/12/1

N2 - Given a tree T = (V, E) of n vertices such that each node v is associated with a value-weight pair (valv, wv), where value val v is a real number and weight wv is a non-negative integer, the density of T is defined as ∑v ∈ V val v/∑v ∈ V wv. A subtree of T is a connected subgraph (V′, E′) of T, where V′ ⊆ V and E′ ⊆ E. Given two integers wmin and wmax, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′ = (V′, E′) satisfying w min ≤ ∑v∈V′ wv ≤ w max. In this paper, we first present an O(wmaxn)-time algorithm to find a weight-constrained maximum-density, path in a tree, and then present an O(wmax 2n)-time algorithm to find a weight-constrained maximum-density subtree in a tree. Finally, given a node subset S ⊂ V, we also present an O(wmax 2n)-time algorithm to find a weight-constrained maximum-density subtree of T which covers all the nodes in S.

AB - Given a tree T = (V, E) of n vertices such that each node v is associated with a value-weight pair (valv, wv), where value val v is a real number and weight wv is a non-negative integer, the density of T is defined as ∑v ∈ V val v/∑v ∈ V wv. A subtree of T is a connected subgraph (V′, E′) of T, where V′ ⊆ V and E′ ⊆ E. Given two integers wmin and wmax, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′ = (V′, E′) satisfying w min ≤ ∑v∈V′ wv ≤ w max. In this paper, we first present an O(wmaxn)-time algorithm to find a weight-constrained maximum-density, path in a tree, and then present an O(wmax 2n)-time algorithm to find a weight-constrained maximum-density subtree in a tree. Finally, given a node subset S ⊂ V, we also present an O(wmax 2n)-time algorithm to find a weight-constrained maximum-density subtree of T which covers all the nodes in S.

UR - http://www.scopus.com/inward/record.url?scp=33744952996&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33744952996&partnerID=8YFLogxK

U2 - 10.1007/11602613_94

DO - 10.1007/11602613_94

M3 - Conference contribution

AN - SCOPUS:33744952996

SN - 3540309357

SN - 9783540309352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 944

EP - 953

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -