Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Bonsai: Growing Interesting Small Trees

Seufert, Stephan and Bedathur, Srikanta and Mestre, Julian and Weikum, Gerhard

MPI-I-2010-5-005. November 2010, 27 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2010-5-005.pdf MPI-I-2010-5-005.pdf 237 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Seufert, Stephan and Bedathur, Srikanta and Mestre, Julian and Weikum, Gerhard},
  TITLE = {Bonsai: Growing Interesting Small Trees},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2010-5-005},
  MONTH = {November},
  YEAR = {2010},
  ISSN = {0946-011X},