×
Mirghorbani, M.; Krokhmal, P.

On finding \(k\)-cliques in \(k\)-partite graphs. (English) Zbl 1276.90061

Optim. Lett. 7, No. 6, 1155-1165 (2013).
Summary: A branch-and-bound algorithm for finding all cliques of size \(k\) in a \(k\)-partite graph is proposed that improves the method of T. Grünert et al. [Comput. Oper. Res. 29, No. 1, 13–31 (2002; Zbl 1032.90034)]. 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 the competitiveness of the developed method.

Cited in 6 Documents

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

maximum clique enumeration problem; \(k\)-partite graph; \(k\)-clique; bit parallelism

Citations:

Zbl 1032.90034
Cite Review PDF
Full Text: DOI

References:

[1] Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization, p. 1–74. Kluwer, Dordrecht (1999) · Zbl 1253.90188
[2] Grabowski S., Fredriksson K.: Bit-parallel string matching under hamming distance in $${{O(n\(\backslash\)lceil m/w \(\backslash\)rceil) O(n\(\backslash\)lceil m/w \(\backslash\)rceil)}}$$ worst case time. Inf. Process. Lett. 105(5), 182–187 (2008) · Zbl 1184.68209 · doi:10.1016/j.ipl.2007.08.021
[3] Grunert T., Irnich S., Zimmermann H.J., Schneider M., Wulfhorst B.: Finding all k-cliques in k-partite graphs, an application in textile engineering. Comput. Oper. Res. 29(1), 13–31 (2002) · Zbl 1032.90034 · doi:10.1016/S0305-0548(00)00053-8
[4] Hyyrö H.: Bit-parallel approximate string matching algorithms with transposition. J. Discrete Algorithms 3(2–4), 215–229 (2005) · Zbl 1101.68504 · doi:10.1016/j.jda.2004.08.006
[5] Hyyrö H., Navarro G.: Bit-parallel witnesses and their applications to approximate string matching. Algorithmica 41(3), 203–231 (2004) · Zbl 1069.68115 · doi:10.1007/s00453-004-1108-z
[6] Krokhmal P., Grundel D., Pardalos P.: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem. Math. Progr. 109(2–3), 525–551 (2007) · Zbl 1147.90033 · doi:10.1007/s10107-006-0036-x
[7] Krokhmal, P.A., Pardalos, P.M.: Limiting optimal values and convergence rates in some combinatorial optimization problems on hypergraph matchings. (2011, submitted)
[8] Leiserson, C.E., Prokop, H., Randall, K.H.: Using de Bruijn sequences to index a 1 in a computer word. Working paper. http://supertech.csail.mit.edu/papers/debruijn.ps (1998)
[9] Liu, Q., Chen, Y.: High functional coherence in k-partite protein cliques of protein interaction networks. In: Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, pp. 111–117 (2009)
[10] Luce R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2), 169–190 (1950) · doi:10.1007/BF02289199
[11] Mirghorbani, M., Krokhmal P., Pasiliao E.L.: Computational studies of randomized multidimensional assignment problems. In: Sorokin, A., Thai, M.T., Pardalos, P.M. (eds.) Dynamics of Information Systems. Springer, Berlin (2012, in press) · Zbl 1268.90066
[12] Peters, M.: CLICK: Clustering categorical data using k-partite maximal cliques. In: IEEE International Conference on Data Engineering (2005)
[13] San Segundo P., Rodríguez-Losada D., Jiminez A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571–581 (2011) · Zbl 1231.90369 · doi:10.1016/j.cor.2010.07.019
[14] Segundo, P., Tapia, C., Puente, J., Rodrguez-Losada, D.: A new exact bit-parallel algorithm for sat. In: ICTAI (2)’08, pp. 59–65 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.