hide
Free keywords:
-
Abstract:
Graphs are increasingly used to model a variety of loosely structured data such
as biological or social networks and entity-relationships. Given this profusion
of large-scale graph data, efficiently discovering interesting substructures
buried
within is essential. These substructures are typically used in determining
subsequent actions, such as conducting visual analytics by humans or designing
expensive biomedical experiments. In such settings, it is often desirable to
constrain the size of the discovered results in order to directly control the
associated costs. In this report, we address the problem of finding
cardinality-constrained connected
subtrees from large node-weighted graphs that maximize the sum of weights of
selected nodes. We provide an efficient constant-factor approximation algorithm
for this strongly NP-hard problem. Our techniques can be applied in a wide
variety
of application settings, for example in differential analysis of graphs, a
problem that frequently arises in bioinformatics but also has applications on
the web.
