Advertisement
Published in:
2005 | OriginalPaper | Chapter
Finding a Weight-Constrained Maximum-Density Subtree in a Tree
Authors : Sun-Yuan Hsieh, Ting-Yu Chou
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a tree
T
=(
V
,
E
) of
n
vertices such that each node
v
is associated with a
value-weight pair
(
val
v
,
w
v
), where
valueval
v
is a real number and
weightw
v
is a non-negative integer, the
density
of
T
is defined as
${\sum_{v \in V^{val_{v}}}} \over {\sum_{v \in V^{w_{v}}}}$
. 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}{\leq} \Sigma_{v\in V^{\prime}}{w_{v}}{\leq} {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, and then present an
O
(
w
max
2
n
)-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
(
w
max
2
n
)-time algorithm to find a weight-constrained maximum-density subtree of
T
which covers all the nodes in
S
.