Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs

DOI10.1007/s00453-019-00656-8zbMath1433.68287OpenAlexW2995561890WikidataQ126548757 ScholiaQ126548757MaRDI QIDQ1987232

Luca Versari, Andrea Marino, Alessio Conte, Roberto Grossi

Publication date: 14 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00656-8

zbMATH Keywords

maximal cliquesenumeration algorithmsspace efficiencypolynomial-time delayreverse searchnetwork mining and analytics

Mathematics Subject Classification ID

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

Related Items

A linear delay algorithm for enumeration of 2-edge/vertex-connected induced subgraphs, Reconfiguration of cliques in a graph, Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, The complexity of dependency detection and discovery in relational databases

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• An efficient algorithm for solving pseudo clique enumeration problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• A note on the problem of reporting maximal cliques
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Enumeration aspects of maximal cliques and bicliques
• On generating all maximal independent sets
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Reverse search for enumeration
• Fast maximal cliques enumeration in sparse graphs
• Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Enumeration Of Labelled Graphs
• Arboricity and Subgraph Listing Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Color-coding
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Listing Triangles
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• The Enumeration of Maximal Cliques of Large Graphs
• Corrections to Bierstone's Algorithm for Generating Cliques
• Algorithm 457: finding all cliques of an undirected graph
• A NOTE ON THE ENUMERATION AND LISTING OF ALL POSSIBLE TREES IN A CONNECTED LINEAR GRAPH
• On cliques in graphs