A short review on the maximum clique problem algorithms with classical, AI, and quantum methods

2024/03/13 by Raffaele Marino, Marino, Raffaele, Lorenzo Buffoni +4 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #Advanced Graph Neural Networks

paper · pdf · doi:10.1038/s42005-026-02606-7

Abstract

Abstract This manuscript provides a comprehensive review of the Maximum Clique Problem, a computational problem that involves finding subsets of vertices in a graph that are all pairwise adjacent to each other. As such, this review is a continuation of the series of previous reviews from 1994, 1999 and 2014. The manuscript covers in a simple way classical algorithms and includes a review of recent developments in graph neural networks and quantum algorithms.

Citations

• Graph Neural Networks: A Review of Methods and Applications
• Learning a SAT Solver from Single-Bit Supervision
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs

Cited by

• A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
• Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking

Related

• Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
• Algorithm for Finding the Maximum Clique Based on Continuous Time Quantum Walk
• Gate-Based and Annealing-Based Quantum Algorithms for the Maximum K-Plex Problem
• A Quantum Circuit to Construct All Maximal Cliques Using Grover Search Algorithm
• The deep learning and statistical physics applications to the problems of combinatorial optimization