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 paper, we address the problem of finding cardinality-constrained
connected subtrees in 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.
