Benchmark Problems for Exhaustive Exact Maximum Clique Search Algorithms

Sándor Szabó, Bogdán Zaválnij

Abstract


There are well established widely used benchmark tests to assess the performance of practical exact clique search algorithms. In this paper a family of further benchmark problems is proposed mainly to test exhaustive clique search procedures.

Full Text:

PDF

References


I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo(1999) The Maximum Clique Problem, Handbook of Combinatorial Optimization Vol. 4, Kluwer Academic Publisher. https://doi.org/10.1007/978-1-4757-3023-4_1

C. Bron and J. Kerbosch (1973) Finding all cliques of an undirected graph, Communications of ACM 16, 575–577. https://doi.org/10.1145/362342.362367

R. Carraghan, P. M. Pardalos (1990) An exact algorithm for the maximum clique problem, Operation Research Letters 9, 375–382. https://doi.org/10.1016/0167-6377(90)90057-C

P. Erd˝os, A. Rényi (1960) On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5, 17–61.

P. Erd˝os (1959), Graph theory and probability, Canad. J. Math. 11, 34–38.

M. R. Garey and D. S. Johnson (2003), Computers and Intractability: A Guide to the Theory of NPcompleteness,Freeman, New York.

R. Hammack, W. Imrich, S. Klavžar (2011) Handbook of Product Graphs, CRC Press, Boca Raton, FL.

J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis (1993) Test case generators and computational results for the maximum clique problem, Journal of Global Optimization 3 ,463–482. http://www.springerlink.com/content/p2m65n57u657605n https://doi.org/10.1007/bf01096415

J. Konc and D. Janežiˇc (2007) An improved branch and bound algorithm for the maximum clique problem, MATCH Communications in Mathematical and Computer Chemistry 58, 569–590.

D. Kumlander (2005) Some Practical Algorithms to Solve the Maximum Clique problem PhD. Thesis, Tallin University of Technology.

C.-M. Li, Z. Quan (2010) An efficient branch-andbound algorithm based on MaxSAT for the maximum clique problem, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence. (AAAI-10), pp. 128–133.

C.-M. Li, Z. Fang, K. Xu (2013) Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem, Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence. (ICTAI2013), pp. 939–946. https://doi.org/10.1109/ictai.2013.143

J. Mycielski (1955) Sur le coloriage des graphes, Colloq. Math. 3, 161–162.

P. R. J. Östergård (2002) A fast algorithm for the maximum clique problem, Discrete Applied Mathematics 120, 197–207. https://doi.org/10.1016/S0166-218X(01)00290-6

C. H. Papadimitriou (1994) Computational Complexity, Addison-Wesley Publishing Company, Inc.

P. San Segundo, D. Rodriguez-Losada, A. Jimenez (2011) An exact bit-parallel algorithm for the maximum clique problem, Computers & OperationsResearch. 38, 571–581. https://doi.org/10.1016/j.cor.2010.07.019

P. San Segundo, F. Matia, D. Rodriguez-Losada, M. Hernando (2013) An improved bit parallel exact maximum clique algorithm, Optimization Letters. 7, 467–479. https://doi.org/10.1007/s11590-011-0431-y

P. San Segundo, C. Tapia (2014) Relaxed approximate coloring in exact maximum clique search, Computers & Operations Research. 44, 185–192. https://doi.org/10.1016/j.cor.2013.10.018

P. San Segundo, A. Nikolaev, M. Batsyn (2015) Infra-chromatic bound for exact maximum clique search, Computers & Operations Research. 64, 293–303. https://doi.org/10.1016/j.cor.2015.06.009

N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs. http://neilsloane.com/doc/graphs.html

S. Szabó (2011) Parallel algorithms for finding cliques in a graph, Journal of Physics: Conference Series 268 012030 https://doi.org/10.1088/1742-6596/268/1/012030

S. Szabó (2013) Monotonic matrices and clique search in graphs, Annales Univ. Sci. Budapest., Sect. Computatorica 41, 307–322.

S. Szabó and B. Zaválnij (2012) Greedy algorithms for triangle free coloring, AKCE International Journal of Graphs and Combinatorics 9 No. 2, 169–186.

E. Tomita and T. Seki (2003) An efficient branch-andbound algorithm for finding a maximum clique, Lecture Notes in Computer Science 2731, 278–289.

E. W. Weisstein, Monotonic Matrix, In: MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/MonotonicMatrix.html

D. R. Wood (1997) An algorithm for finding a maximum clique in a graph, Oper. Res. Lett. 21, 211–217. https://doi.org/10.1016/S0167-6377(97)00054-0




DOI: https://doi.org/10.31449/inf.v43i2.2678

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.