A Novel and Practical Algorithmic Enhancement for Enumerating Maximal and Maximum k-Partite Cliques in k-Partite Graphs

A k-partite graph is one whose vertices can be partitioned into k disjoint partite sets, with edges allowed between but not within these sets. In such a graph, a maximal k-partite clique is a subgraph with at least one vertex from each partite set and every allowable edge such that the subgraph cannot be enlarged by the incorporation of additional vertices. A maximum k-partite clique is of course a maximal k-partite clique of the greatest size. The results reported here describe a novel and practical modification of the best previously published algorithm for the enumeration of these special subgraphs. The relative performance of this new method relies on implicit edge addition and search tree pruning and is evaluated on graphs constructed from both pseudorandom and real-world data.