Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1996, pp. 16–29 Submitted: November 20, 1996. Published: April 4, 1996.

POLYNOMIAL-TIME PARTITION OF A GRAPH INTO CLIQUES

Anatoly D. Plotnikov

Abstract. The properties of finite partially ordered set are used to get solution of the partition finding problem of arbitrary undirected graph into the minimum number of cliques. The solving algorithm has a partical orientation. The run time of the solving algorithm is equal to O(n^{5}), where n is number vertices of graph.

(1991) A.M.S. Subject Classification Codes. 05.

Key Words and Phrases. Clique, Graph, partial order.

Department of Applied Mathematics and Computing Systems, Vinnitsa State Techical University, Vinnitsa, Ukraine E-mail Address: vstu@sovam.com \begin{matrix}c \\ ◯ \end{matrix}1996 Cameron University

Typeset by AMS-TEX