direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Algorithmic Explorations Between Cliques and 2-Clubs

Mervin Triphaus (Master Thesis Defence TU Berlin)


The search of internally dense subgraphs, so-called clusters, in network structures is for several decades an internationally established discipline in applied informatics. It is applied in various domains like bioinformatics to detect clusters in so-called Protein-Protein interaction networks (PPI networks), in telecommunications to detect interference between links in wireless networks or also in detecting communities in social networks. One approach of defining clusters are t-robust 2-clubs. These are subgraphs of diameter two which have t-many paths of length at most two between each vertex pair. The edge density of t-robust 2-clubs depends on the size of the subgraph itself. In order to remove this dependency, γ-relative robust 2-clubs were defined. They are a variation of t-robust 2-clubs, where the required number of paths is parameterized by γ, relative to the amount of vertices in the subgraph. In this thesis we studied structural properties of γ-relative robust 2-clubs and developed a fixed parameter tractable (FPT) algorithm to detect these subgraphs. Furthermore we developed a method to separate the graph into multiple subgraphs. Our experiments show that our algorithm performs well if these subgraphs are small.


Mervin Triphaus
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras