Inhalt des Dokuments
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
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.
Back to the research colloquium site.