Carleton University
Technical Report TR-05-03
April 15, 2005
A New Approach for Solving the Maximum Clique Problem
Peter J. Taillon
Abstract
In this report, we describe an improved exact algorithm for solving the Maximum Clique problem in a graph using a novel sampling technique combined with the FPT k-vertex cover algorithm. We also introduce a very effective heuristic for finding a maximum clique that combines our sampling approach with fast independent set approximation. Experimental research indicates that this approach matches or outperforms the current best algorithms for finding a maximum clique in a graph, with significantly smaller runtimes.