Abstract
In this paper we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value \(\delta \). The obtained increase in performance reaches 70 % on benchmark instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173, 1–17 (2006)
Li, C.M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, pp. 344–351. IEEE (2010)
San Segundo, P., Rodriguez-Losada, D., Matia, F., Galan, R.: Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl. Intell. 32, 311–329 (2010)
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, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191–203. Springer, Heidelberg (2010)
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242, 693–709 (2015)
Acknowledgments
The authors would like to thank Chu-Min Li and Zhe Quan for the source code of their MaxCLQ algorithm. We gratefully acknowledge their kindness. The work was conducted at National Research University Higher School of Economics and supported by RSF grant 14-41-00039.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Nikolaev, A., Batsyn, M., Segundo, P.S. (2015). Reusing the Same Coloring in the Child Nodes of the Search Tree for the Maximum Clique Problem. In: Dhaenens, C., Jourdan, L., Marmion, ME. (eds) Learning and Intelligent Optimization. LION 2015. Lecture Notes in Computer Science(), vol 8994. Springer, Cham. https://doi.org/10.1007/978-3-319-19084-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-19084-6_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19083-9
Online ISBN: 978-3-319-19084-6
eBook Packages: Computer ScienceComputer Science (R0)