×

A much faster branch-and-bound algorithm for finding a maximum clique. (English) Zbl 1475.68253

Zhu, Daming (ed.) et al., Frontiers in algorithmics. 10th international workshop, FAW 2016, Qingdao, China, June 30 – July 2, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9711, 215-226 (2016).
Summary: We present improvements to a branch-and-bound maximum-clique-finding algorithm MCS [E. Tomita et al., Lect. Notes Comput. Sci. 5942, 191–203 (2010; Zbl 1274.05455)] that was shown to be fast. First, we employ an efficient approximation algorithm for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named MCT. It is shown that MCT is much faster than MCS by extensive computational experiments. In particular, MCT is shown to be faster than MCS for gen400_p0.9_75 and gen400_p0.9_65 by over 328,000 and 77,000 times, respectively.
For the entire collection see [Zbl 1407.68047].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25 Approximation algorithms
68W40 Analysis of algorithms

Citations:

Zbl 1274.05455

Software:

MaxCliqueDyn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.M.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27, 397-416 (2014) · Zbl 1290.90063 · doi:10.1007/s10878-012-9592-6
[2] http://www.nlsde.buaa.edu.cn/ kexu/benchmarks/graph-benchmarks.htm
[3] Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, Supplement, vol. A, pp. 1-74. Kluwer Academic Publishers, Boston (1999) · Zbl 1253.90188 · doi:10.1007/978-1-4757-3023-4_1
[4] Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375-382 (1990) · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C
[5] Fujii, T., Tomita, E.: On efficient algorithms for finding a maximum clique, Technical report of IECE, AL81-113, 25-34 (1982)
[6] Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability. DIMACS Series in DMTCS, vol. 26. American Mathematical Society, Boston (1996) · Zbl 0875.68678
[7] Katayama, K., Hamamoto, A., Narihisa, H.: An effective local search for the maximum clique problem. Inf. Process. Lett. 95, 503-511 (2005) · Zbl 1185.68283 · doi:10.1016/j.ipl.2005.05.010
[8] Kohata, Y., Nishijima, T., Tomita, E., Fujihashi, C., Takahashi, H.: Efficient algorithms for finding a maximum clique, Technical report of IEICE, COMP89-113, 1-8 (1990)
[9] 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) · Zbl 1274.05452
[10] Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. In: AAAI Conference on AI, pp. 128-133 (2010)
[11] Li, C.M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: Proceedings of the IEEE ICTAI, pp. 344-351 (2010)
[12] Maslov, E., Batsyn, M., Pardalos, P.M.: Speeding up branch and bound algorithms for solving the maximum clique problem. J. Glob. Optim. 59, 1-21 (2014) · Zbl 1294.05124 · doi:10.1007/s10898-013-0075-9
[13] Segundo, P.S., Nikolaev, A., Batsyn, M.: Infra-chromatic bound for exact maximum clique search. Comput. Oper. Res. 64, 293-303 (2015) · Zbl 1349.90825 · doi:10.1016/j.cor.2015.06.009
[14] Sutani, Y., Higashi, T., Tomita, E., Takahashi, S., Nakatani, H.: A faster branch-and-bound algorithm for finding a maximum clique, Technical report of IPSJ, 2006-AL-108, 79-86 (2006) · Zbl 1274.05455
[15] Tomita, E., Kohata, Y., Takahashi, H.: A simple algorithm for finding a maximum clique, Technical report of the Univ. of Electro-Commun., UEC-TR-C5(1) (1988)
[16] Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol. 2731, pp. 278-289. Springer, Heidelberg (2003) · Zbl 1038.68565 · doi:10.1007/3-540-45066-1_22
[17] Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37, 95-111 (2007) · Zbl 1127.90079 · doi:10.1007/s10898-006-9039-7
[18] 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) · Zbl 1274.05455 · doi:10.1007/978-3-642-11440-3_18
[19] Tomita, E., Sutani, Y., Higashi, T., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique with computational experiments. IEICE Trans. Inf. Syst. E96-D, 1286-1298 (2013) · Zbl 1274.05455 · doi:10.1587/transinf.E96.D.1286
[20] Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242, 693-709 (2015) · Zbl 1341.05241 · doi:10.1016/j.ejor.2014.09.064
[21] Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the STOC 2006, pp. 681-690 (2006) · Zbl 1301.68152
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.