Abstract
This work concentrates on finding maximum clique from undirected and unweighted graphs. Maximum clique problem is one of the most known NP-complete problems, the most complex problems of NP class. A lot of other problems can be transformed into clique problem, therefore solving or at least finding a faster algorithm for finding clique will automatically help to solve lots of other tasks. The main contribution of this work is a new exact algorithm for finding maximum clique, which works faster than any currently existing algorithm on a wide variety of graphs. The main idea is to combine a number of efficient improvements from different algorithms into a new one. At first sight these improvements cannot cooperate together, but a new approach of skipping vertices from further expanding instead of pruning the whole branch allows to use all the upgrades at ones. There will be some step-by-step examples with explanations which demonstrate how to use a proposed algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of Np-Completeness. Freeman, New York (2003)
Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158 (1971)
Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375–382 (1990)
Östergård, P.R.J.: A fast algorithm for the maximum clique problem. Discret. Appl. Math. 120, 197–207 (2002)
Kumlander, D.: Some Practical Algorithms to Solve the Maximum Clique Problem. Tallinn University of Technology, Tallinn (2005)
Clarkson, K.: A modification to the greedy algorithm for vertex cover. Inf. Process. Lett. 16(1), 23–25 (1983)
Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525–547 (2012)
Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science, DMTCS’03. Springer-Verlag, Berlin, Heidelberg, pp. 278–289 (2003)
Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95–111 (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: Proceedings of the 4th International Conference on Algorithms and Computation, WALCOM’10. Springer-Verlag, Berlin, Heidelberg, pp. 191–203 (2010)
Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.M.: Improvements to MCS Algorithm for the Maximum Clique Problem. Springer Science+Business Media, New York (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kumlander, D., Porošin, A. (2020). Reversed Search Maximum Clique Algorithm Based on Recoloring. In: Le Thi, H., Le, H., Pham Dinh, T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019. Advances in Intelligent Systems and Computing, vol 991. Springer, Cham. https://doi.org/10.1007/978-3-030-21803-4_46
Download citation
DOI: https://doi.org/10.1007/978-3-030-21803-4_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21802-7
Online ISBN: 978-3-030-21803-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)