Benchmark Problems for Exhaustive Exact Maximum Clique Search Algorithms

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.

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

Authors

  • Sándor Szabó
  • Bogdán Zaválnij Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences

DOI:

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

Downloads

Additional Files

Published

06/15/2019

How to Cite

Szabó, S., & Zaválnij, B. (2019). Benchmark Problems for Exhaustive Exact Maximum Clique Search Algorithms. Informatica, 43(2). https://doi.org/10.31449/inf.v43i2.2678

Issue

Vol. 43 No. 2 (2019)

Section

Regular papers

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.