An algorithm for finding all maximal complete subgraphs and an estimate of the order of computational complexity

This paper develops an algorithm for finding all maximal complete subgraphs or cliques of an undirected graph. The algorithm is simple, and is based on a refinement of the technique of successive splitting described by Paull and Unger in the determination of maximal compatibles of states in the context of minimization of incomplete sequential machines. The proposed algorithm tends to reduce computation in generating the subgraphs for problems most generally encountered, particularly in relation to the applicability in sequential switching theory.