Algorithm 457: finding all cliques of an undirected graph

1973/09/01 by Coen Bron, Joep Kerbosch · 62 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.1145/362342.362367

Abstract

bttroductian. A maximal complete subgraph (clique) is a complete subgraph that is not contained in any other complete subgraph.

Cited by

• Emergent Traveling Waves in Neural Circuits
• A Graph-Based Control Interface for Traffic Signals on Heterogeneous Road Networks
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• The Complexity of Enumeration and Reliability Problems
• A Hybrid Graph Representation for Exact Graph Algorithms
• Methods for Analyzing RNA Pseudoknots via Chord Diagrams and Intersection Graphs
• On the Codebook Design for NOMA Schemes from Bent Functions
• Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
• Aggregating maximal cliques in real-world graphs
• A Systematic Analysis of Out-of-Distribution Detection Under Representation and Training Paradigm Shifts
• Optimizing Kernel Discrepancies via Subset Selection
• The X-ray structure of Brassica napus β-keto acyl carrier protein reductase and its implications for substrate binding and catalysis
• Wireless Network Scheduling with Discrete Propagation Delays: Theorems and Algorithms
• A Comprehensive Empirical and Theoretical Analysis of Batching Algorithms for Efficient, Safe, Parallel Mutation Analysis in Rust
• A framework for quantifying individual and collective common sense
• Rarely categorical, highly separable representations along the cortical hierarchy
• On Self-Dual Quantum Codes, Graphs, and Boolean Functions
• Encoding computationally hard problems in triangular Rydberg atom arrays
• Approximate Closest Community Search in Networks
• Node Classification via Simplicial Interaction with Augmented Maximal Clique Selection
• Spotting Suspicious Reviews via (Quasi-)clique Extraction
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Examining the differential risk from high-level artificial intelligence and the question of control
• Distribution Estimation for Global Data Association via Approximate Bayesian Inference
• Network location and learning: the influence of network resources and firm capabilities on alliance formation
• Efficient Large-Scale Multiple Migration Planning and Scheduling in SDN-enabled Edge Computing
• Subgraphs and motifs in a dynamic airline network
• Dyadically resolving trinomials for fast modular arithmetic
• Graph theory-based automated quantum algorithm for efficient querying of acyclic and multiloop causal configurations
• HiTeC: Hierarchical Contrastive Learning on Text-Attributed Hypergraph with Semantic-Aware Augmentation
• On Throughput and Decoding Delay Performance of Instantly Decodable Network Coding
• Guarding Networks Through Heterogeneous Mobile Guards
• Crystal structure and active site location of N-(1-D-carboxylethyl)-L-norvaline dehydrogenase
• Robustness Verification of Tree-based Models
• New algorithms for k-degenerate graphs
• Dynamics of Opinions with Bounded Confidence in Social Cliques: Emergence of Fluctuations
• Listing Maximal Subgraphs in Strongly Accessible Set Systems
• A comprehensive analysis of 40 blind protein structure predictions. [europepmc]
• Comparative promoter region analysis powered by CORG. [europepmc]
• Comparison of protein interaction networks reveals species conservation and divergence. [europepmc]
• Evidence for systems-level molecular mechanisms of tumorigenesis. [europepmc]
• Using ESTs for phylogenomics: can one accurately infer a phylogenetic tree from a gappy alignment? [europepmc]
• Application of 3D Zernike descriptors to shape-based ligand similarity searching. [europepmc]
• Small Molecule Subgraph Detector (SMSD) toolkit. [europepmc]
• A knowledge-guided strategy for improving the accuracy of scoring functions in binding affinity prediction. [europepmc]
• Co-expression module analysis reveals biological processes, genomic gain, and regulatory mechanisms associated with breast cancer progression. [europepmc]
• A systematic comparison of genome-scale clustering algorithms. [europepmc]
• ParsEval: parallel comparison and analysis of gene structure annotations. [europepmc]
• Cortical high-density counterstream architectures. [europepmc]
• On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. [europepmc]
• PharmDock: a pharmacophore-based docking program. [europepmc]
• Efficient prediction of human protein-protein interactions at a global scale. [europepmc]
• A multi-tissue genome-scale metabolic modeling framework for the analysis of whole plant systems. [europepmc]
• ToPASeq: an R package for topology-based pathway analysis of microarray and RNA-Seq data. [europepmc]
• Algebraic Topology of Multi-Brain Connectivity Networks Reveals Dissimilarity in Functional Patterns during Spoken Communications. [europepmc]
• Functional Geometry of Human Connectomes. [europepmc]
• A deep learning framework to predict binding preference of RNA constituents on protein surface. [europepmc]
• Large-scale network analysis captures biological features of bacterial plasmids. [europepmc]
• Equine Facial Action Coding System for determination of pain-related facial responses in videos of horses. [europepmc]
• Arabidopsis Coexpression Tool: a tool for gene coexpression analysis in Arabidopsis thaliana . [europepmc]
• Estimating the Similarity between Protein Pockets. [europepmc]
• Extraordinary selection on the human X chromosome associated with archaic admixture. [europepmc]

Related

• Finding Cliques of a Graph using Prime Numbers
• A Polynomial Time Algorithm For Solving Clique Problems
• A Novel Approach Applied to the Largest Clique Problem
• Constant Approximating k-Clique is W[1]-hard
• A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem