{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T16:40:02Z","timestamp":1748796002077,"version":"3.41.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,3,2]],"date-time":"2016-03-02T00:00:00Z","timestamp":1456876800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","award":["DPI 2010-21247-C02-01"],"award-info":[{"award-number":["DPI 2010-21247-C02-01"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000935","name":"Russell Sage Foundation","doi-asserted-by":"publisher","award":["14-41-00039"],"award-info":[{"award-number":["14-41-00039"]}],"id":[{"id":"10.13039\/100000935","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s11590-016-1019-3","type":"journal-article","created":{"date-parts":[[2016,3,2]],"date-time":"2016-03-02T08:47:12Z","timestamp":1456908432000},"page":"343-358","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A parallel maximum clique algorithm for large and massive sparse graphs"],"prefix":"10.1007","volume":"11","author":[{"given":"Pablo","family":"San Segundo","sequence":"first","affiliation":[]},{"given":"Alvaro","family":"Lopez","sequence":"additional","affiliation":[]},{"given":"Jorge","family":"Artieda","sequence":"additional","affiliation":[]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,2]]},"reference":[{"key":"1019_CR1","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller R.E., Thatcher J.\u00a0W., (eds.) Complexity of computer computations. New York, 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1019_CR2","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.1093\/bioinformatics\/btq100","volume":"26","author":"J Konc","year":"2010","unstructured":"Konc, J., Janezic, D.: ProBiS algorithm for detection of structurally similar protein binding sites by local structural alignment. Bioinformatics 26, 1160\u20131168 (2010)","journal-title":"Bioinformatics"},{"key":"1019_CR3","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1186\/1471-2105-13-S10-S5","volume":"13","author":"J Eblen","year":"2012","unstructured":"Eblen, J., Phillips, C., Rogers, G., Langston, M.: The maximum clique enumeration problem: algorithms, applications, and implementations. BMC Bioinf. 13, S5 (2012)","journal-title":"BMC Bioinf."},{"volume-title":"Clustering Challenges in Biological Networks","year":"2009","key":"1019_CR4","unstructured":"Butenko, S., Chaovalitwongse, W., Pardalos, P. (eds.): Clustering Challenges in Biological Networks. World Scientific, Singapore (2009)"},{"key":"1019_CR5","doi-asserted-by":"crossref","unstructured":"Segundo San, P., Artieda, J.: A novel clique formulation for the visual feature matching problem. Appl. Intell. 43(2), 325\u2013342 (2015)","DOI":"10.1007\/s10489-015-0646-1"},{"key":"1019_CR6","doi-asserted-by":"crossref","unstructured":"Segundo San, P., Rodriguez-Losada, D., Mat\u00eda, F., Gal\u00e1n, R.: Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl. Intell. 32(3), 311\u2013329 (2010)","DOI":"10.1007\/s10489-008-0147-6"},{"key":"1019_CR7","unstructured":"San Segundo, P., Rodriguez-Losada, D.: Robust global feature based data association with a sparse bit optimized maximum clique algorithm. IEEE Tran. Robot. (T_RO), 29(5), 1332\u20131339 (2013)"},{"key":"1019_CR8","doi-asserted-by":"crossref","unstructured":"Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. Proc. Discret. Math. Theor. Comput. Sci. LNCS 2731, 278\u2013289 (2003)","DOI":"10.1007\/3-540-45066-1_22"},{"key":"1019_CR9","first-page":"191","volume":"5942","author":"E Tomita","year":"2010","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. LNCS 5942, 191\u2013203 (2010)","journal-title":"LNCS"},{"key":"1019_CR10","doi-asserted-by":"crossref","unstructured":"Segundo San, P., Rodriguez-Losada, D., Jimenez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571\u2013581 (2011)","DOI":"10.1016\/j.cor.2010.07.019"},{"key":"1019_CR11","doi-asserted-by":"crossref","unstructured":"Segundo San, P., Matia, F., Rodriguez-Losada, D., Hernando, M.: An improved bit parallel exact maximum clique algorithm. Optim. Lett. 7(3), 467\u2013479 (2013)","DOI":"10.1007\/s11590-011-0431-y"},{"key":"1019_CR12","doi-asserted-by":"crossref","unstructured":"San Segundo, P., Tapia, C.: Relaxed approximate coloring in exact maximum clique search Comput. Oper. Res. 44, 185\u2013192 (2014)","DOI":"10.1016\/j.cor.2013.10.018"},{"key":"1019_CR13","doi-asserted-by":"publisher","unstructured":"San Segundo, P., Nikolaev, A., Batsyn, M.: Infra-chromatic bound for exact maximum clique search, (2015). doi: 10.1016\/j.cor.2015.06.009","DOI":"10.1016\/j.cor.2015.06.009"},{"key":"1019_CR14","doi-asserted-by":"crossref","unstructured":"Chu-Min, L., Zhiwen, F., Ke, X.: Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem. Proc. Tools Artif. Intell. (ICTAI), 939\u2013946 (2013)","DOI":"10.1109\/ICTAI.2013.143"},{"issue":"9","key":"1019_CR15","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"key":"1019_CR16","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375\u2013382 (1990)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1019_CR17","first-page":"97","volume":"120","author":"PRJ \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P.R.J.: A fast algorithm for the maximum clique problem. Discret. Appl. Math. 120(1), 97\u2013207 (2002)","journal-title":"Discret. Appl. Math."},{"key":"1019_CR18","first-page":"569","volume":"58","author":"J Konc","year":"2007","unstructured":"Konc, J., Jane\u017ei\u010d, D.: An improved branch-and-bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58, 569\u2013590 (2007)","journal-title":"MATCH Commun. Math. Comput. Chem."},{"issue":"4","key":"1019_CR19","doi-asserted-by":"crossref","first-page":"545","DOI":"10.3390\/a5040545","volume":"5","author":"P Prosser","year":"2012","unstructured":"Prosser, P.: Exact algorithms for maximum clique: a computational study. Algorithms 5(4), 545\u2013587 (2012)","journal-title":"Algorithms"},{"issue":"3","key":"1019_CR20","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693\u2013709 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"1019_CR21","doi-asserted-by":"crossref","unstructured":"Pardalos, P. M., Rappe, J., Resende, M.: An exact parallel algorithm for the maximum clique problem. In: High Performance Algorithms and Software in Nonlinear Optimization, pp. 279\u2013300. Kluwer Academic Publishers, Dordrecht (1998)","DOI":"10.1007\/978-1-4613-3279-4_18"},{"issue":"4","key":"1019_CR22","doi-asserted-by":"crossref","first-page":"618","DOI":"10.3390\/a6040618","volume":"6","author":"C McCreesh","year":"2013","unstructured":"McCreesh, C., Prosser, P.: Multi-Threading a state-of-the-art maximum clique algorithm. Algorithms 6(4), 618\u2013635 (2013)","journal-title":"Algorithms"},{"key":"1019_CR23","doi-asserted-by":"crossref","unstructured":"Depolli, M., Konc, J., Rozman, K., Trobec, R., Jane\u017ei\u010d, D.: Exact parallel maximum clique algorithm for general and protein graphs. J. Chem. Inf. Model. 53(9), 2212\u20132228 (2013) (source code available at\u00a0 http:\/\/commsys.ijs.si\/~matjaz\/maxclique\/ )","DOI":"10.1021\/ci4002525"},{"key":"1019_CR24","doi-asserted-by":"crossref","unstructured":"Rossi, R., Gleich, D., Assefaw,G., Mostofa, Md.: Fast maximum clique algorithms for large graphs. Proc. World Wide Web Companion Conf., 365\u2013366 (2014) (source code available at https:\/\/www.cs.purdue.edu\/homes\/dgleich\/codes\/maxcliques )","DOI":"10.1145\/2567948.2577283"},{"key":"1019_CR25","doi-asserted-by":"crossref","unstructured":"Pattabiraman, B., Ali Patwary, M., Gebremedhin, A., Liao, W., Choudhary, A.: Fast algorithms for the maximum clique problem on massive sparse graphs. LNCS 8305, 156\u2013169 (2013) (source code available at http:\/\/cucis.ece.northwestern.edu\/projects\/MAXCLIQUE )","DOI":"10.1007\/978-3-319-03536-9_13"},{"issue":"4","key":"1019_CR26","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","volume":"15","author":"E Balas","year":"1986","unstructured":"Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM J Comput 15(4), 1054\u20131068 (1986)","journal-title":"SIAM J Comput"},{"key":"1019_CR27","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02020444","volume":"17","author":"P Erd\u00f6s","year":"1966","unstructured":"Erd\u00f6s, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Mathematica Academiae Scientiarum Hungarica 17, 61\u201399 (1966)","journal-title":"Acta Mathematica Academiae Scientiarum Hungarica"},{"key":"1019_CR28","unstructured":"BITSCAN C++ library. https:\/\/www.biicode.com\/pablodev\/bitscan . Accessed 1 Feb 2016"},{"key":"1019_CR29","unstructured":"Biicode, a dependency manager for C++. https:\/\/www.biicode.com . Accessed 1 Feb 2016"},{"key":"1019_CR30","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman, S.B.: Network structure and minimum degree. Social Netw. 5, 269\u2013287 (1983)","journal-title":"Social Netw."},{"key":"1019_CR31","unstructured":"Batagelj,V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks. arXiv:cs\/0310049v1 (2003)"},{"key":"1019_CR32","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Prosser, P.: The shape of the search tree for the maximum clique problem and the implications for parallel branch-and-bound. ACM Trans. Parallel Comput. 2(1), Article 8 (2015)","DOI":"10.1145\/2742359"},{"key":"1019_CR33","unstructured":"The Network Data Repository. http:\/\/networkrepository.com\/ . Accessed 1 Feb 2016"},{"key":"1019_CR34","unstructured":"Source code for BBMCPara and BBMCSP. https:\/\/www.biicode.com\/pablodev\/copt . Accessed 1 Feb 2016"},{"key":"1019_CR35","unstructured":"OpenMP specification. http:\/\/openmp.org\/wp\/ . Accessed 1 Feb 2016"},{"key":"1019_CR36","unstructured":"Full single-core tests: http:\/\/venus.elai.upm.es\/logs\/results_sparse\/ Full multi-core tests: http:\/\/venus.elai.upm.es\/logs\/results_parallel\/ . Accessed 1 Feb 2016"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1019-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-016-1019-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1019-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1019-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T15:58:19Z","timestamp":1748793499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-016-1019-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,2]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["1019"],"URL":"https:\/\/doi.org\/10.1007\/s11590-016-1019-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2016,3,2]]}}}