TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 11.02.2016

isti-logo

Page Content

to Navigation

Enumerating Maximal Cliques in Temporal Graphs

Anne-Sophie Himmel (TU Berlin)

In many complex systems, interactive dynamics play a very important role in the analysis of such systems. A modeling framework to capture these dynamics are temporal graphs. Our main focus lies on the extension of the concept of cliques to temporal graphs: for a given time period $\Delta$, a Delta-clique in temporal graphs is a set of vertices and a time interval, such that all vertices interact with each other at least after every Delta time steps within the time interval.
A greedy algorithm which enumerates all maximal Delta-cliques in a temporal graph was already introduced. In contrast to this approach, we apply the Bron-Kerbosch algorithm---an efficient, recursive backtracking algorithm which enumerates all maximal cliques in simple graphs---to this problem. Experiments on real-world datasets show that there is a significant improvement in the running time in comparison to the greedy algorithm approach.


Date
Speaker
Location
Language
11.02.2016
16:15
Anne-Sophie Himmel
TEL 512
English

 

Back to the research colloquium site.

 

 

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe