Theoretical underpinnings for maximal clique enumeration on perturbed graphs

DOI10.1016/j.tcs.2010.03.011zbMath1209.05243OpenAlexW2086428708WikidataQ57439775 ScholiaQ57439775MaRDI QIDQ974747

Matthew C. Schmidt, Paul Breimyer, William Hendrix, 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

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

Uses Software

• Algorithm 457

Cites Work

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

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