Theoretical underpinnings for maximal clique enumeration on perturbed graphs

DOI10.1016/J.TCS.2010.03.011zbMATH Open1209.05243DBLPjournals/tcs/HendrixSBS10OpenAlexW2086428708WikidataQ57439775 ScholiaQ57439775MaRDI QIDQ974747FDOQ974747

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

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

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)

Cites Work

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

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

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)