An output sensitive algorithm for maximal clique enumeration in sparse graphs

DOI10.4230/LIPICS.IPEC.2017.27MaRDI QIDQ5111887zbMATHFDO

Authors George Manoussakis

Publication date 27 May 2020

zbMATH Keywords

\(k\)-degenerate graphsmaximal cliquesenumeration algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Recommendations

• Listing all maximal cliques in sparse graphs in near-optimal time
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Listing all maximal cliques in large sparse real-world graphs
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs

Cites work

• k-Degenerate Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• A Space-Economical Suffix Tree Construction Algorithm
• A note on the problem of reporting maximal cliques
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• Algorithms on Strings, Trees and Sequences
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Arboricity and Subgraph Listing Algorithms
• Fast maximal cliques enumeration in sparse graphs
• Listing all maximal cliques in large sparse real-world graphs
• On cliques in graphs
• On generating all maximal independent sets
• On-line construction of suffix trees
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(7)

• A new decomposition technique for maximal clique enumeration for sparse graphs
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Listing all maximal cliques in sparse graphs in near-optimal time
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Efficient enumeration of maximal induced bicliques
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: An output sensitive algorithm for maximal clique enumeration in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111887)