Abstract: The maximum clique problem (MCP) is to determine a sub graph of maximum cardinality. A clique is a sub graph in which all pairs of vertices are mutually adjacent. Based on existing surveys, the main goal of this paper is to provide a simplified version and comprehensive review on Maximum clique problem. This review intends to encourage and motivate new researchers in this area. Though capturing the complete literature in this regard is beyond scope of the paper, but it is tried to capture most of the representative papers from similar approaches.

 

Keywords: Maximum Clique problem, Exact Algorithms, Approximation Algorithms, Heuristic Approach, Local search.