Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications

DOI10.1007/978-3-319-53925-6_1MaRDI QIDQ2980894zbMATH OpenOpenAlexFDO

Authors Etsuji Tomita

Publication date 5 May 2017

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-53925-6_1

zbMATH Keywords

branch-and-bound depth-first search algorithmsenumeration of all maximal cliques

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2040957
• Exact algorithms for maximum clique: a computational study
• Efficient algorithms for finding maximum cliques of an overlap graph
• A fast algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• Algorithm Theory - SWAT 2004
• Efficient algorithms for clique problems
• An algorithm for finding a maximum clique in a graph
• A new algorithm for the maximum clique problem

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A review on algorithms for maximum clique problems
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• An effective local search for the maximum clique problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An improved branch and bound algorithm for the maximum clique problem
• Clique relaxation models in social network analysis
• Clique-detection models in computational biochemistry and genomics
• Computing and Combinatorics
• Fast local search for the maximum independent set problem
• Finding a Maximum Independent Set
• Improvements to MCS algorithm for the maximum clique problem
• Infra-chromatic bound for exact maximum clique search
• Listing all maximal cliques in large sparse real-world graphs
• On cliques in graphs
• Speeding up branch and bound algorithms for solving the maximum clique problem
• The maximum clique problem
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(10)

• An Efficient Algorithm for Enumerating Pseudo Cliques
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Refined pivot selection for maximal clique enumeration in graphs
• Analysis of reactive search optimisation techniques for the maximum clique problem and applications. (Summary)
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• A review on algorithms for maximum clique problems
• An algorithm for reporting maximal \(c\)-cliques
• Exact algorithms for maximum clique: a computational study

Describes a project that uses

Uses Software

• Algorithm 457
• MaxCliqueDyn

This page was built for publication: Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980894)