ANALYSIS OF THE RANDOMIZED ALGORITHM FOR CLIQUE PROBLEMS

摘要

In this paper, two modifications of the clique problem are addressed: the Maximum Clique Problem and the k-Clique Problem, respectively. Simple randomized algorithm whose variants are able to solve both of the above problems is provided. The essential part of this paper contains a probabilistic analysis of the algorithm. Moreover, its behavior is compared with other known algorithms and its overall performance and parallelization are discussed.