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 -