AN ALGORITHM FOR THE DECOMPOSITION OF GRAPHS INTO CLIQUES

Chung (F.R. K. Chung, On the decomposition of graphs, SIAM J. Algebrai c Discrete Methods 2 (1981), 1-12.) and independently Gyori and Kostoc hka (E. Gyori and A,V. Kostochka, On a problem of G. O. H. Katona and T. Tarjan, Acta Math. Acad. Sci. Hung. 34 (1979), 321-327.) proved the following theorem: For any graph G with n vertices, the edge set E(G) can be decomposed into cliques such that the sum of the orders of the cliques is at most [n(2)/2]. In this paper, we give a polynomial algo rithm for the decomposition of E(G) into cliques which satisfies the c ondition of the theorem. The time required for this algorithm is at mo st O(n(3)). The algorithm may be regarded as a support for Winkler's c onjecture posed in P. Winkler (Problem 27, Discrete Math. 101 (1992), 359-360). (C) 1995 John Wiley & Sons, Inc.