The Maximum Clique Problem

The Maximum Clique Problem

1999 | Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, Marcello Pelillo
The maximum clique problem is a classical problem in combinatorial optimization with significant applications across various domains. This paper provides a survey of results regarding algorithms, complexity, and applications of the problem, along with an updated bibliography. It builds upon previous works with similar objectives. The paper is structured into eight sections. The first section introduces the problem, including notations and definitions. The second section presents problem formulations, including integer and continuous formulations. The third section discusses computational complexity. The fourth section covers bounds and estimates. The fifth section presents exact algorithms, including enumerative algorithms and exact algorithms for both unweighted and weighted cases. The sixth section explores heuristics, including sequential greedy, local search, advanced search, and continuous-based heuristics. The seventh section highlights selected applications in coding theory, geometry of tiling, fault diagnosis, and computer vision. The eighth section concludes the paper. References are provided for further reading. The authors are Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo, all from different institutions in Austria, Italy, and the United States. The paper aims to provide a comprehensive overview of the maximum clique problem, its formulations, algorithms, complexity, and applications.The maximum clique problem is a classical problem in combinatorial optimization with significant applications across various domains. This paper provides a survey of results regarding algorithms, complexity, and applications of the problem, along with an updated bibliography. It builds upon previous works with similar objectives. The paper is structured into eight sections. The first section introduces the problem, including notations and definitions. The second section presents problem formulations, including integer and continuous formulations. The third section discusses computational complexity. The fourth section covers bounds and estimates. The fifth section presents exact algorithms, including enumerative algorithms and exact algorithms for both unweighted and weighted cases. The sixth section explores heuristics, including sequential greedy, local search, advanced search, and continuous-based heuristics. The seventh section highlights selected applications in coding theory, geometry of tiling, fault diagnosis, and computer vision. The eighth section concludes the paper. References are provided for further reading. The authors are Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo, all from different institutions in Austria, Italy, and the United States. The paper aims to provide a comprehensive overview of the maximum clique problem, its formulations, algorithms, complexity, and applications.
Reach us at info@study.space
[slides and audio] The Maximum Clique Problem