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
    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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references