Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
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.