Some Improvements on Kumlander-s Maximum Weight Clique Extraction Algorithm

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.

• Satoshi Shimizu
• Kazuaki Yamaguchi
• Toshiki Saitoh
• Sumio Masuda

• Maximum weight clique
• exact algorithm
• branch-andbound
• NP-hard.

[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