Decompositions of the maximum clique problem

Schmidt, Peter (2013) Decompositions of the maximum clique problem. Pollack Periodica, 8 (1). pp. 167-178. ISSN 1788-1994

Text pollack.8.2013.1.15.pdf Restricted to Repository staff only until 30 April 2033. Download (372kB)

Abstract

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.

Actions (login required)

Edit Item