Theoretical underpinnings for maximal clique enumeration on perturbed graphs

DOI10.1016/J.TCS.2010.03.011MaRDI QIDQ974747zbMATH OpenOpenAlexDBLPWikidataFDO

Authors William Hendrix, Matthew C. Schmidt, Paul Breimyer, Nagiza F. Samatova

Publication date 7 June 2010

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

Full work available at URL https://doi.org/10.1016/j.tcs.2010.03.011

zbMATH Keywords

graph algorithmsgraph perturbation theorymaximal clique enumerationuncertain and noisy data

Mathematics Subject Classification ID

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

Recommendations

• Enumerating maximal cliques in large sparse graphs
• Finding all maximal cliques in dynamic graphs
• Efficiently enumerating all maximal cliques with bit-parallelism
• A linear time algorithm for maximal clique enumeration in large sparse graphs
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 1256640 (Why is no real title available?)
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• Arboricity and Subgraph Listing Algorithms
• Cliques of a graph-variations on the Bron-Kerbosch algorithm
• Distributed approximate matching
• Finding all maximal cliques in dynamic graphs
• On cliques in graphs
• On generating all maximal independent sets
• The Enumeration of Maximal Cliques of Large Graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(4)

• Computing maximum \(k\)-defective cliques in massive graphs
• Maximal clique enumeration in finding near neighbourhoods
• Enumeration aspects of maximal cliques and bicliques
• Finding all maximal cliques in dynamic graphs

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Theoretical underpinnings for maximal clique enumeration on perturbed graphs

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