The worst-case time complexity for generating all maximal cliques and computational experiments

DOI10.1016/j.tcs.2006.06.015zbMath1153.68398OpenAlexW2160429376WikidataQ56210444 ScholiaQ56210444MaRDI QIDQ860810

Akira Tanaka, Haruhisa Takahashi, Etsuji Tomita

Publication date: 9 January 2007

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

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

zbMATH Keywords

computational experiments enumeration maximal cliques worst-case time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (74)

Topological graph persistence ⋮ Communicability graph and community structures in complex networks ⋮ Accurate optimization models for interference constrained bandwidth allocation in cellular networks ⋮ Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ A linear time algorithm for maximal clique enumeration in large sparse graphs ⋮ An extended depth-first search algorithm for optimal triangulation of Bayesian 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 ⋮ Set covering problem with conflict constraints ⋮ An efficient algorithm for solving pseudo clique enumeration problem ⋮ Computing maximal subsemigroups of a finite semigroup ⋮ Use of a novel grammatical inference approach in classification of amyloidogenic hexapeptides ⋮ Efficiently enumerating all maximal cliques with bit-parallelism ⋮ Mining preserving structures in a graph sequence ⋮ On comparing algorithms for the maximum clique problem ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ Constant amortized time enumeration of Eulerian trails ⋮ A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Toward uniform random generation in 1-safe Petri nets ⋮ Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs ⋮ Characteristics of the maximal independent set ZDD ⋮ Novel centrality metrics for studying essentiality in protein‐protein interaction networks based on group structures ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ Computing maximal cliques in link streams ⋮ Stable fixed points of combinatorial threshold-linear networks ⋮ Refined pivot selection for maximal clique enumeration in graphs ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Unnamed Item ⋮ Stochastic stability in best shot network games ⋮ SQBC: an efficient subgraph matching method over large and dense graphs ⋮ Fast maximal cliques enumeration in sparse graphs ⋮ Enumerating maximal cliques in link streams with durations ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Local community detection in complex networks based on maximum cliques extension ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ An Efficient Algorithm for Enumerating Pseudo Cliques ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Exact algorithms for maximum clique: a computational study ⋮ On the termination of some biclique operators on multipartite graphs ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ A new decomposition technique for maximal clique enumeration for sparse graphs ⋮ Efficient enumeration of maximal induced bicliques ⋮ K-plex cover pooling for graph neural networks ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ A note on the problem of reporting maximal cliques ⋮ General cut-generating procedures for the stable set polytope ⋮ Recognition of split-graphic sequences ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Theoretical underpinnings for maximal clique enumeration on perturbed graphs ⋮ Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem ⋮ Preprocessing and cutting planes with conflict graphs ⋮ Structural interpretation of sparse fault data using graph theory and geological rules. Fault data interpretation ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ Large-scale clique cover of real-world networks ⋮ Multi-agent coordination over local indexes via clique-based distributed assignment ⋮ Optimizing synchronizability in networks of coupled systems ⋮ An improved upper bound on maximal clique listing via rectangular fast matrix multiplication ⋮ Unnamed Item ⋮ Parallel Algorithm for Enumerating Maximal Cliques in Complex Network ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Fuzzy Clustering based on Coverings ⋮ Isolation concepts for clique enumeration: comparison and computational experiments ⋮ Finding weighted \(k\)-truss communities in large networks ⋮ Enumerating Isolated Cliques in Synthetic and Financial Networks ⋮ The variational quantum eigensolver: a review of methods and best practices ⋮ Synthesizing cubes to satisfy a given intersection pattern

Uses Software

Cites Work

This page was built for publication: The worst-case time complexity for generating all maximal cliques and computational experiments