A linear time algorithm for maximal clique enumeration in large sparse graphs

DOI10.1016/J.IPL.2017.05.005MaRDI QIDQ2628285zbMATH OpenOpenAlexFDO

Authors Ting Yu, Mengchi Liu

Publication date 13 June 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.05.005

zbMATH Keywords

computational complexitydata structuresgraph algorithmslinear time algorithmsmaximal clique enumeration

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Enumerating maximal cliques in large sparse graphs
• Fast maximal cliques enumeration in sparse graphs
• Algorithm Theory - SWAT 2004
• Listing all maximal cliques in large sparse real-world graphs
• Listing all maximal cliques in sparse graphs in near-optimal time

Cites work

• A clique-detection algorithm based on neighborhoods in graphs
• A note on the problem of reporting maximal cliques
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• Algorithm 457: finding all cliques of an undirected graph
• Efficient algorithms for clique problems
• Enumerating all connected maximal common subgraphs in two graphs
• Finding all maximal cliques in dynamic graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(10)

• Fast maximal cliques enumeration in sparse graphs
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• On CLIQUE Problem for Sparse Graphs of Large Dimension
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• Enumerating maximal cliques in large sparse graphs
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• A parallel maximum clique algorithm for large and massive sparse graphs
• Algorithms – ESA 2005
• Theoretical underpinnings for maximal clique enumeration on perturbed graphs

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: A linear time algorithm for maximal clique enumeration in large sparse graphs

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