Computing maximal cliques in link streams

DOI10.1016/j.tcs.2015.09.030zbMath1331.68158arXiv1502.00993OpenAlexW1890592509MaRDI QIDQ897884

Matthieu Latapy, Clémence Magnien, Jordan Viard

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.00993

zbMATH Keywords

cliquestemporal networkstime-varying graphslink streams

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ A new temporal interpretation of cluster editing ⋮ Efficient temporal core maintenance of massive graphs ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Temporal interval cliques and independent sets ⋮ On atomic cliques in temporal graphs ⋮ How fast can we reach a target vertex in stochastic temporal graphs? ⋮ Enumerating maximal cliques in link streams with durations ⋮ Temporal Vertex Cover with a Sliding Time Window ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Graph signatures: identification and optimization ⋮ Computing parameters of sequence-based dynamic graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Temporal vertex cover with a sliding time window ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An information-theoretic framework for the lossy compression of link streams ⋮ Temporal matching ⋮ Sliding window temporal graph coloring ⋮ Temporal cliques admit sparse spanners ⋮ The temporal explorer who returns to the base ⋮ How fast can we reach a target vertex in stochastic temporal graphs ⋮ Temporal Cliques Admit Sparse Spanners

Uses Software

• cliques
• Algorithm 457

Cites Work

• The worst-case time complexity for generating all maximal cliques and computational experiments
• A note on the problem of reporting maximal cliques
• On generating all maximal independent sets
• Enumerating all connected maximal common subgraphs in two graphs
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm 457: finding all cliques of an undirected graph

This page was built for publication: Computing maximal cliques in link streams