An enhanced bitstring encoding for exact maximum clique search in sparse graphs

References

• D.V. Andrade, M.G.C. Resende, and R.F. Werneck, Fast local search for the maximum independent set problem, J. Heuristics 18(4) (2012), pp. 525–547. doi: 10.1007/s10732-012-9196-4
   Web of Science ®Google Scholar
• D.K.C. Bahadur, T. Akutsu, E. Tomita, T. Seki, and A. Fujijama, Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms, Genome Inform. 13 (2006), pp. 143–152.
   Google Scholar
• E. Balas and C.S. Yu, Finding a maximum clique in an arbitrary graph, SIAM J. Comput. 15(4) (1986), pp. 1054–1068. doi: 10.1137/0215075
   Web of Science ®Google Scholar
• V. Batagelj and M. Zaversnik, An O(m) Algorithm for Cores Decomposition of Networks, Computing Research Repository. Vol. cs.DS/0310, 2003.
   Google Scholar
• H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool, Speeded-up robust features (SURF), Comput. Vis. Image Underst. 110(3) (2008), pp. 346–359. doi: 10.1016/j.cviu.2007.09.014
   Web of Science ®Google Scholar
• BBMC family of algorithms. Available at https://www.biicode.com/pablodev/examples_clique. Accessed 1/2/16.
   Google Scholar
• BITSCAN C++ library. Available at https://www.biicode.com/pablodev/bitscan. Accessed 1/2/16.
   Google Scholar
• I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization (supp. Vol. A), D.-Z. Du and P.M. Pardalos, eds., Springer, Boston, 1999, pp. 1–74.
   Google Scholar
• C. Bron and J. Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Commun. ACM 16(9) (1973), pp. 575–577. doi: 10.1145/362342.362367
   Web of Science ®Google Scholar
• S. Butenko, W. Chaovalitwongse, and P. Pardalos, eds. Clustering Challenges in Biological Networks, World Scientific, Singapore, 2009.
   Google Scholar
• R. Carraghan and P.M. Pardalos, An exact algorithm for the maximum clique problem, Oper. Res. Lett. 9 (1990), pp. 375–382. doi: 10.1016/0167-6377(90)90057-C
   Web of Science ®Google Scholar
• L. Chu-Min, F. Zhiwen, and X. Ke, Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem, Proc. Tools with Artificial Intelligence (ICTAI), Washington, DC, 2013, pp. 939–946.
   Google Scholar
• P. Erdös and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung. 17 (1966), pp. 61–99. doi: 10.1007/BF02020444
   Web of Science ®Google Scholar
• T. Fahle, Simple and Fast: Improving a Branch-and-bound Algorithm for Maximum Clique, 10th Annual European Symposium on Algorithms (ESA-02), London, 2002, pp. 485–498.
   Google Scholar
• Information concerning this work. Available at http://venus.elai.upm.es/logs/results_watched/. Accessed 1/2/16.
   Google Scholar
• R. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations, R. Miller, J. Thatcher, and J. Bohlinger, eds., Springer, Boston, 1972, pp. 85–103.
   Google Scholar
• J. Konc and D. Janežič, An improved branch and bound algorithm for the maximum clique problem, MATCH Commun. Math. Comput. Chem. 58 (2007), pp. 569–590.
   Web of Science ®Google Scholar
• D.W. Matula, G. Marble, and J.D. Issacson, Graph coloring algorithms, in Graph Theory and Computing, R.C. Read, ed., Academic Press, New York, 1972, pp. 109–122.
   Google Scholar
• P.R.J. Östergård, A fast algorithm for the maximum clique problem, Discrete Appl. Math. 120(1) (2002), pp. 97–207.
   Web of Science ®Google Scholar
• PMC algorithm. Available at http://ryanrossi.com/pmc/. Accessed 1/2/16.
   Google Scholar
• P. Prosser, Exact algorithms for maximum clique: A computational study, Algorithms 5(4) (2012), pp. 545–587. doi: 10.3390/a5040545
   Google Scholar
• R. Rossi, D. Gleich, G. Assefaw, and Md. Mostofa, Fast Maximum Clique Algorithms for Large Graphs, Proceedings of World Wide Web Companion Conference (WW Companion’14), Florence, 2014, pp. 365–366.
   Google Scholar
• P. San Segundo and J. Artieda, A novel clique formulation for the visual feature matching problem, Appl. Intell. 43(2) (2015), pp. 325–342. doi: 10.1007/s10489-015-0646-1
   Web of Science ®Google Scholar
• P. San Segundo, A. Lopez, and P.M. Pardalos, A new exact maximum clique algorithm for large and massive sparse graphs, Comput. Oper. Res. 66 (2016), pp. 81–94. doi: 10.1016/j.cor.2015.07.013
   Web of Science ®Google Scholar
• P. San Segundo, F. Matia, D. Rodriguez-Losada, and M. Hernando, An improved bit parallel exact maximum clique algorithm, Optim. Lett. 7(3) (2013), pp. 467–479. doi: 10.1007/s11590-011-0431-y
   Web of Science ®Google Scholar
• P. San Segundo, A. Nikolaev, and M. Batsyn, Infra-chromatic bound for exact maximum clique search, Comput. Oper. Res. 64 (2015), pp. 293–303. doi: 10.1016/j.cor.2015.06.009
   Web of Science ®Google Scholar
• P. San Segundo, D. Rodríguez-Losada, and A. Jimenez, An exact bit-parallel algorithm for the maximum clique problem, Comput. Oper. Res. 38(2) (2011), pp. 571–581. doi: 10.1016/j.cor.2010.07.019
   Web of Science ®Google Scholar
• P. San Segundo, D. Rodríguez-Losada, F. Matía, and R. Galán, Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver, Appl. Intell. 32(3) (2010), pp. 311–329. doi: 10.1007/s10489-008-0147-6
   Web of Science ®Google Scholar
• P. San Segundo and C. Tapia, Relaxed approximate coloring in exact maximum clique search, Comput. Oper. Res. 44 (2014), pp. 185–192. doi: 10.1016/j.cor.2013.10.018
   Web of Science ®Google Scholar
• N.J.A. Sloane, Challenge problems: independent sets in graphs. Available at http://neilsloane.com/doc/graphs.html. Accessed 1/2/16.
   Google Scholar
• C. Strecha, W. von Hansen, L. Van Gool, P. Fua, and U. Thoennessen, On Benchmarking Camera Calibration and Multi-View Stereo for High Resolution Imagery, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Anchorage, AK, 2008, pp. 1–8.
   Google Scholar
• The Network Data Repository. Available at http://networkrepository.com/. Accessed 1/2/16.
   Google Scholar
• E. Tomita and T. Seki, An Efficient Branch and Bound Algorithm for Finding a Maximum Clique, Proceedings of the Discrete Mathematics and Theoretical Computer Science, LNCS 2731, Dijon, 2003, pp. 278–289.
   Google Scholar
• E. Tomita, Y. Sutani, T. Higashi, S. Takahashi, and M. Wakatsuki, A simple and faster branch-and-bound algorithm for finding a maximum clique, in WALCOM: Algorithms and Computation. WALCOM 2010, M.S. Rahman and S. Fujita eds., Lecture Notes in Computer Science, Vol. 5942, Springer, Berlin, 2010, pp. 191–203.
   Google Scholar
• Q. Wu and J.K. Hao, An adaptive multistart tabu search approach to solve the maximum clique problem, J. Comb. Optim. 26(1) (2013), pp. 86–108. doi: 10.1007/s10878-011-9437-8
   Web of Science ®Google Scholar
• Q. Wu and J.K. Hao, A review on algorithms for maximum clique problems, Eur. J. Oper. Res. 242(3) (2015), pp. 693–709. doi: 10.1016/j.ejor.2014.09.064
   Web of Science ®Google Scholar