Algorithm 457: finding all cliques of an undirected graph

DOI10.1145/362342.362367zbMath0261.68018OpenAlexW2116007667WikidataQ56210395 ScholiaQ56210395MaRDI QIDQ5677064

Joep Kerbosch, Coen Bron

Publication date: 1973

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/362342.362367

Mathematics Subject Classification ID

Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (only showing first 100 items - show all)

Complexity and performance of a graph theory algorithm for cluster analysis† ⋮ Non-existence of (76,30,8,14) strongly regular graph ⋮ Solving the maximum clique problem using a tabu search approach ⋮ Protein classification by matching and clustering surface graphs ⋮ Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem ⋮ Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ A linear time algorithm for maximal clique enumeration in large sparse graphs ⋮ Multilevel approaches for large-scale proteomic networks ⋮ All roads lead to Rome -- new search methods for the optimal triangulation problem ⋮ On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs ⋮ On CLIQUE Problem for Sparse Graphs of Large Dimension ⋮ Efficient bounds on a branch and bound algorithm for graph colouration ⋮ A global optimization approach for solving the maximum clique problem ⋮ The Quadratic Multiknapsack Problem with Conflicts and Balance Constraints ⋮ An algorithm for finding a maximum weighted independent set in an arbitrary graph ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ Attribute selection using contranominal scales ⋮ A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation ⋮ Persistent topological features of dynamical systems ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization ⋮ An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem ⋮ Recursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problem ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows ⋮ Extended formulations for perfect domination problems and their algorithmic implications ⋮ Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks ⋮ Enumerating Independent Linear Inferences ⋮ Exact and metaheuristic methods for a real-world examination timetabling problem ⋮ Discovering the hidden community structure of public transportation networks ⋮ Unnamed Item ⋮ Detecting capital market convergence clubs ⋮ On the Approximability of the Minimum Weight $t$-partite Clique Problem ⋮ An efficient algorithm for maximum entropy extension of block-circulant covariance matrices ⋮ Testing One Hypothesis Multiple Times: The Multidimensional Case ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ Noise-Robust Modes of the Retinal Population Code Have the Geometry of “Ridges” and Correspond to Neuronal Communities ⋮ On computing large temporal (unilateral) connected components ⋮ Standardization of the input data in classification problems using the descent vector method ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ A GENETIC ALGORITHM FOR DETECTING COMMUNITIES IN LARGE-SCALE COMPLEX NETWORKS ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ K-plex cover pooling for graph neural networks ⋮ Bayes linear analysis for ordinary differential equations ⋮ DEUM - Distribution Estimation Using Markov Networks ⋮ MN-EDA and the Use of Clique-Based Factorisations in EDAs ⋮ Speeding up branch and bound algorithms for solving the maximum clique problem ⋮ Fast circular arc segmentation based on approximate circularity and cuboid graph ⋮ A branch and bound algorithm for the maximum clique problem ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ A note on bimatrix game maximal Selten subsets ⋮ On the chromatic numbers of small-dimensional Euclidean spaces ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Multifidelity Information Fusion Algorithms for High-Dimensional Systems and Massive Data sets ⋮ An algorithm for obtaining the chromatic number and an optimal coloring of a graph ⋮ Clique-detection models in computational biochemistry and genomics ⋮ A fast discovery algorithm for large common connected induced subgraphs ⋮ Components in time-varying graphs ⋮ Unnamed Item ⋮ Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering ⋮ Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem ⋮ Structural interpretation of sparse fault data using graph theory and geological rules. Fault data interpretation ⋮ Local multiple alignment via subgraph enumeration ⋮ Complementarity in finite quantum mechanics and computer-aided computations of complementary observables ⋮ Clique analysis of a tolerance relation ⋮ Supervised classification of high-dimensional correlated data: application to genomic data ⋮ Large-scale clique cover of real-world networks ⋮ Slack matrices, \(k\)-products, and 2-level polytopes ⋮ Flow formulations for curriculum-based course timetabling ⋮ The degree of parallelism in generalized stochastic network ⋮ Learning to sample initial solution for solving 0-1 discrete optimization problem by local search ⋮ New anomaly free supergravities in six dimensions ⋮ Local search for diversified top-\(k\) clique search problem ⋮ A new approximate cluster deletion algorithm for diamond-free graphs ⋮ Community detection in complex networks: from statistical foundations to data science applications ⋮ LeaDCD: leadership concept-based method for community detection in social networks ⋮ Enumerating all maximal biclusters in numerical datasets ⋮ Faster maximal clique enumeration in large real-world link streams ⋮ Hierarchical overlapping community detection for weighted networks ⋮ Detecting strong cliques in co-authorship networks ⋮ Unnamed Item ⋮ Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms ⋮ Parallel Algorithm for Enumerating Maximal Cliques in Complex Network ⋮ Characterizing the complexity of time series networks of dynamical systems: A simplicial approach ⋮ A classification for community discovery methods in complex networks ⋮ Close-to-optimal algorithm for rectangular decomposition of 3D shapes ⋮ Cliques of a graph-variations on the Bron-Kerbosch algorithm ⋮ Using Fifth Generation Tools for Solving the Clique Number Problem ⋮ Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements ⋮ Sampling-based box-covering algorithm for renormalization of networks ⋮ Unnamed Item ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs ⋮ Synthesizing cubes to satisfy a given intersection pattern ⋮ Game Theory Explorer: software for the applied game theorist ⋮ On the uniform duality in copositive optimization ⋮ Lower bounds on paraclique density

This page was built for publication: Algorithm 457: finding all cliques of an undirected graph