Some Improvements on Kumlander-s Maximum Weight Clique Extraction Algorithm

Authors: Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, Sumio Masuda

Abstract:

Some fast exact algorithms for the maximum weight clique problem have been proposed. Östergard’s algorithm is one of them. Kumlander says his algorithm is faster than it. But we confirmed that the straightforwardly implemented Kumlander’s algorithm is slower than O¨ sterga˚rd’s algorithm. We propose some improvements on Kumlander’s algorithm.

Keywords: Maximum weight clique, exact algorithm, branch-andbound, NP-hard.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081051

References:

[1] D. Kumlander, "On importance of a special sorting in the maximumweight clique algorithm based on colour classes," Proc. of the second international conference on Modelling, Computation and Optimization in Information Systems and Management Sciences Communications in Computer and Information Science Volume 14, 2008, pp 165-174.
[2] D. Kumlander, http://www.kumlander.eu/graph/
[3] K. Yamaguchi, S. Masuda, "A new exact algorithm for the maximum weight clique problem," Proc. of the 23rd International Technical Conference on Circuits/Systems, Computers and Communications 2008, pp. 317 - 320.
[4] M.R. Garey and D.S. Johonson,, Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
[5] P.R.J. O¨ sterga˚rd, "A new algorithm for the maximum-weight clique problem," Nordic Journal of Computing, vol. 8, pp.424-436, 2001.
[6] P.R.J. O┬¿ sterga╦Ürd, http://users.tkk.fi/Ôê╝pat/cliquer.html
[7] E. Tomita, Y. Sutani, T. Higashi, S. Takahashi, M. Wakatsuki, "A simple and faster branch-and-bound algorithm for finding a maximum clique," Proc. of the 4th International Workshop, WALCOM Algorithms and Computation Lecture Notes in Computer Science Volume 5942, 2010, pp 191-203