2005 | OriginalPaper | Buchkapitel
Finding a Weight-Constrained Maximum-Density Subtree in a Tree
verfasst von : Sun-Yuan Hsieh, Ting-Yu Chou
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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
.