A fast algorithm for the maximum clique problem
By Patric R. J. Östergård. Discrete Applied Mathematics, 2002
656 citations recorded by the source corpus.
Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem--which is computationally equivalent to the maximum independent (stable) set problem--is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/b5b8f6cec279e59c2d7aeb463b149d87eb702edc
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- A review on algorithms for maximum clique problems (2015, neutral): “Comparative studies of exact algorithms are available in a number of studies like Carmo & Züge (2012); Konc & Janežič (2007); Li & Quan (2010); Österg̊ard (2002); Prosser (2012); Régin (2003); Segundo, Matia, Rodriguez-Losada, & Hernando (2013); Segundo, Rodŕıguez-Losada, & Jiménez (2011); Tomita &”
- An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts (2008, methodology): “The CLIQUER package is composed of a set of C routines for finding cliques in an arbitrary weighted graph based on the exact branch-and-bound algorithm developed by Östergård [40].”