Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications

DOI10.1007/978-3-319-53925-6_1zbMath1487.05254OpenAlexW2588222785MaRDI QIDQ2980894

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) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms

Uses Software

• MaxCliqueDyn
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infra-chromatic bound for exact maximum clique search
• Fast local search for the maximum independent set problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An effective local search for the maximum clique problem
• The maximum clique problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Improvements to MCS algorithm for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• A review on algorithms for maximum clique problems
• Clique Relaxation Models in Social Network Analysis
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Finding a Maximum Independent Set
• A New Algorithm for Generating All the Maximal Independent Sets
• Computing and Combinatorics
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs

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