On finding k-cliques in k-partite graphs

M. Mirghorbani, P. Krokhmal

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In this paper, a branch-and-bound algorithm for finding all cliques of size k in a k-partite graph is proposed that improves upon the method of Grunert et al. (in Comput Oper Res 29(1):13-31, 2002). The new algorithm uses bit-vectors, or bitsets, as the main data structure in bit-parallel operations. Bitsets enable a new form of data representation that improves branching and backtracking of the branch-and-bound procedure. Numerical studies on randomly generated instances of k-partite graphs demonstrate competitiveness of the developed method.

Original languageEnglish (US)
Pages (from-to)1155-1165
Number of pages11
JournalOptimization Letters
Issue number6
StatePublished - Aug 2013


  • Bit parallelism
  • Maximum clique enumeration problem
  • k-Clique
  • k-Partite graph

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'On finding k-cliques in k-partite graphs'. Together they form a unique fingerprint.

Cite this