Decompositions of the maximum clique problem
Peter Schmidt · Pollack Periodica · 2013
Maximal clique enumeration and maximum clique generation are well known NP-complete discrete optimization problems. Researchers experiment with parallel implementations of known algorithms in order to speed up the resolution process. Parallel implementations are equivalent to divisions of the feasible region that is an implicit decomposition of the original problem. The below study looks for the possible ways of explicit decomposition, which can subsequently serve as bases of parallel algorithms. The paper introduces formally the notion of decomposition, specifies explicit algorithms for different sorts of decomposition, provides and compares decomposition based algorithms for the maximum clique problem.