Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation (Q2401518)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation |
scientific article |
Statements
Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation (English)
0 references
1 September 2017
0 references
A continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix is presented. A one-to-one correspondence between stationary points of the authors' formulation and cliques of a given graph is built. It is shown that the local (resp. global) minima of the continuous problem correspond to the maximal (resp. maximum) cliques of the given graph. A new clique finding algorithm based on the continuous formulation is presented. The efficiency of the new algorithm is tested on the DIMACS data sets to show that it outperforms other existing algorithms based on the Motzkin-Straus formulation and that it can compete with a sophisticated combinatorial heuristic.
0 references
clique problem
0 references
Motzkin-Straus formulation
0 references
clique finding algorithm
0 references
rank-one non-negative matrix approximation
0 references
0 references