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

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

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

• 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
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• 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

(11)

• Exact algorithms for maximum clique: a computational study
• 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
• A review on algorithms for maximum clique problems
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• Distributed algorithms for maximum cliques
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• An Efficient Algorithm for Enumerating Pseudo Cliques
• An algorithm for reporting maximal \(c\)-cliques
• Refined pivot selection for maximal clique enumeration in graphs

Describes a project that uses

Uses Software

• MaxCliqueDyn
• Algorithm 457

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)