|
Abstract : |
We present a heuristic scheme for finding a clique of maximum size or weight. Our heuristic scheme uses approximation techniques for the weighted vertex cover problem, due to R. Bar-Yehuda and S. Even [BE85]. The approach is based on the notion of making incremental progress towards finding a clique. At each step of our algorithm, one or more local optimization techniques are attempted, and when these techniques do not make progress, we perform local approximations. In the local approximation step, the algorithm selects a heuristic from a set of heuristics, depending on the characteristics of the graph at that stage. Once a solution is constructed, we attempt to iteratively refine the solution. Randomization plays a key role at various steps of our algorithm. 1, |
