On finding k-cliques in k-partite graphs

M. Mirghorbani; P. Krokhmal

doi:10.1007/s11590-012-0536-y

On finding k-cliques in k-partite graphs

M. Mirghorbani
, P. Krokhmal

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	1155-1165
Number of pages	11
Journal	Optimization Letters
Volume	7
Issue number	6
DOIs	https://doi.org/10.1007/s11590-012-0536-y
State	Published - Aug 2013
Externally published	Yes

Keywords

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

ASJC Scopus subject areas

Business, Management and Accounting (miscellaneous)
Control and Optimization

Access to Document

10.1007/s11590-012-0536-y

Cite this

@article{691e400dcdaf4f1783d1bf5f4036690c,

title = "On finding k-cliques in k-partite graphs",

abstract = "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.",

keywords = "Bit parallelism, Maximum clique enumeration problem, k-Clique, k-Partite graph",

author = "M. Mirghorbani and P. Krokhmal",

note = "Funding Information: Acknowledgments The authors would like to acknowledge partial support of AFOSR Grant FA9550-12-1-0142 and NSF Grant EPS1101284.",

year = "2013",

month = aug,

doi = "10.1007/s11590-012-0536-y",

language = "English (US)",

volume = "7",

pages = "1155--1165",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "6",

}

TY - JOUR

T1 - On finding k-cliques in k-partite graphs

AU - Mirghorbani, M.

AU - Krokhmal, P.

N1 - Funding Information: Acknowledgments The authors would like to acknowledge partial support of AFOSR Grant FA9550-12-1-0142 and NSF Grant EPS1101284.

PY - 2013/8

Y1 - 2013/8

N2 - 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.

AB - 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.

KW - Bit parallelism

KW - Maximum clique enumeration problem

KW - k-Clique

KW - k-Partite graph

UR - https://www.scopus.com/pages/publications/84880851239

UR - https://www.scopus.com/pages/publications/84880851239#tab=citedBy

U2 - 10.1007/s11590-012-0536-y

DO - 10.1007/s11590-012-0536-y

M3 - Article

AN - SCOPUS:84880851239

SN - 1862-4472

VL - 7

SP - 1155

EP - 1165

JO - Optimization Letters

JF - Optimization Letters

IS - 6

ER -

On finding k-cliques in k-partite graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this