direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments

Manuel Sorge (TU Berlin)

We consider the following problem. Given a graph and a rational number µ, 0<µ<1, find a connected subgraph of density at least µ with the largest number of vertices. Here, the density of an n-vertex graph with m edges is m/binom(n,2). This problem arises in many application contexts such as community detection in social networks. We implement a branch and bound algorithm and tune it for efficiency on sparse real-world graphs for the case µ=1/2. Central issues for the implementation are the choice of branching candidates, two new upper bounding procedures, and several data reduction and early termination rules.

Joint work with Christian Komusiewicz and Kolja Stahl.

Manuel Sorge
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras