Polynomial-time partition of a graph into cliques.
Anatoly D. Plotnikov · 1996
The properties of a finite partially ordered set are used to find the solution of the part i tion finding problem of an arbitrary undirected graph into the minimum number of cliques. The solving algorithm has a practical application. The run time of the solving algorithm is equal to O(n 5 ), where n is the number of vertices of the graph. (1991) A.M.S. (MOS) Subject Classification codes: 05. Keywords and Phrases. Graph, clique, partial order, vertex-saturated. 1 Statement of the problem. We will consider the class Ln of undirected n-graphs without loops and multiple edges. Let G = (X; \\Gamma) 2 Ln , where X = fx 1 ; : : : ; xng is the set of vertices of the graph G, \\Gamma is mapping of X into X. The set N ae X creates a clique of the graph G if the correlation x i 2 \\Gammax j takes place for any x i ; x j 2 N (i 6= j; 8i; j 2 f1; 2; : : : ; ng). The clique of graph G, defined by the set of vertices N , we will denote: Q(N ). In the special case, when Card(N ) = 1, we will call ...