Abstract
This paper describes new improvements for BB-MaxClique (San Segundo et al. in Comput Oper Resour 38(2):571–581, 2011), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, pp 191–203, 2010), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB-MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.
Similar content being viewed by others
References
Karp, R.M.: In: Miller, R.E., Thatcher, J.W. (eds.) Reducibility among Combinatorial Problems, pp. 85–103. Plenum, New York (1972)
Bahadur D.K.C., Akutsu T., Tomita E., Seki T., Fujijama A.: Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms. Genome Inform. 13, 143–152 (2006)
Butenko S., Wilhelm W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Operat. Res. 173, 1–17 (2006)
Hotta K., Tomita E., Takahashi H.: A view invariant human FACE detection method based on maximum cliques. Trans. IPSJ 44(SIG14(TOM9)), 57–70 (2003)
San Segundo P., Rodríguez-Losada D., Matía F., Galán R.: Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl. Intel. 32(3), 311–329 (2010)
Bomze I.M., Budinich M., Pardalos P.M., Pelillo M.: HandBook of Combinatorial Optimization. Supplement A, pp. 1–74. Kluwer Academic Publishers, Dordrecht (1999)
Wood D.R.: An algorithm for finding a maximum clique in a graph. Operat. Res. Lett. 21, 211–217 (1977)
Carraghan R., Pardalos P.M.: An exact algorithm for the maximum clique problem. Operat. Res. Lett. 9, 375–382 (1990)
Östergård P.R.J.: A fast algorithm for the maximum clique problem. Discrete Applied Mathematics 120(1), 97–207 (2002)
Tomita, E., Seki, T.: An efficient branch and bound algorithm for finding a maximum clique. In: Calude, C., Dinneen, M., Vajnovszki, V. (eds) Discrete Mathematics and Theoretical Computer Science. LNCS, vol. 2731, pp. 278–289, Springer, Berlin (2003)
Konc J., Janečič D.: An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58, 569–590 (2007)
Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Rahman MS, Fujita S. (eds.) Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol. 5942, pp. 191–203. Springer, Berlin (2010)
San Segundo, P., Rodriguez-Losada, D., Jimenez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Resour. 38(2), 571–581 (2011)
Johnson, D.S., Trick, M.A. (eds): Cliques, coloring and Satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26. American Mathematical Society, Providence (1996)
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Chaff, S.M.: Engineering an efficient SAT solver. In: XXXVIII Proceedings of Design Automation Conference (DAC ’01), pp. 530–535. ACM, New York (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
San Segundo, P., Matia, F., Rodriguez-Losada, D. et al. An improved bit parallel exact maximum clique algorithm. Optim Lett 7, 467–479 (2013). https://doi.org/10.1007/s11590-011-0431-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0431-y