{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:08:31Z","timestamp":1749874111912,"version":"3.41.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319514680"},{"type":"electronic","value":"9783319514697"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-51469-7_26","type":"book-chapter","created":{"date-parts":[[2016,12,24]],"date-time":"2016-12-24T21:23:01Z","timestamp":1482614581000},"page":"306-316","source":"Crossref","is-referenced-by-count":0,"title":["An Enhanced Infra-Chromatic Bound for the Maximum Clique Problem"],"prefix":"10.1007","author":[{"given":"Pablo","family":"San Segundo","sequence":"first","affiliation":[]},{"given":"Jorge","family":"Artieda","sequence":"additional","affiliation":[]},{"given":"Rafael","family":"Leon","sequence":"additional","affiliation":[]},{"given":"Cristobal","family":"Tapia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,25]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4757-3023-4_1","volume-title":"Handbook of Combinatorial Optimization","author":"I Bomze","year":"1999","unstructured":"Bomze, I., Budinich, M., Pardalos, P., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 4, pp. 1\u201374. Springer, New York (1999)"},{"volume-title":"Clustering Challenges in Biological Networks","year":"2009","key":"26_CR2","unstructured":"Butenko, S., Chaovalitwongse, W., Pardalos, P. (eds.): Clustering Challenges in Biological Networks. World Scientific, Singapore (2009)"},{"issue":"3","key":"26_CR3","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s10489-008-0147-6","volume":"32","author":"P San Segundo","year":"2010","unstructured":"San Segundo, P., Rodriguez-Losada, P., Matia, D., Galan, R.: Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl. Intell. 32(3), 311\u2013329 (2010)","journal-title":"Appl. Intell."},{"key":"26_CR4","first-page":"1","volume":"99","author":"P San Segundo","year":"2013","unstructured":"San Segundo, P., Rodriguez-Losada, D.: Robust global feature based data association with a sparse bit optimized maximum clique algorithm. IEEE Trans. Robot. 99, 1\u20137 (2013)","journal-title":"IEEE Trans. Robot."},{"issue":"2","key":"26_CR5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10489-015-0646-1","volume":"43","author":"P San Segundo","year":"2015","unstructured":"San Segundo, P., Artieda, J.: A novel clique formulation for the visual feature matching problem. Appl. Intell. 43(2), 325\u2013342 (2015)","journal-title":"Appl. Intell."},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/3-540-45749-6_44","volume-title":"Algorithms \u2014 ESA 2002","author":"T Fahle","year":"2002","unstructured":"Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 485\u2013498. Springer, Heidelberg (2002). doi: 10.1007\/3-540-45749-6_44"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-45066-1_22","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"E Tomita","year":"2003","unstructured":"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\u2013289. Springer, Heidelberg (2003). doi: 10.1007\/3-540-45066-1_22"},{"issue":"2","key":"26_CR8","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","volume":"38","author":"P San Segundo","year":"2011","unstructured":"Segundo, S., Rodriguez-Losada, D, Jimenez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571\u2013581 (2011)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"26_CR9","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s11590-011-0431-y","volume":"7","author":"P San Segundo","year":"2013","unstructured":"San Segundo, P., Matia, F., Rodriguez-Losada, D., Hernando, M.: An improved bit parallel exact maximum clique algorithm. Optim. Lett. 7(3), 467\u2013479 (2013)","journal-title":"Optim. Lett."},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.cor.2013.10.018","volume":"44","author":"P San Segundo","year":"2014","unstructured":"San Segundo, P., Tapia, C.: Relaxed approximate coloring in exact maximum clique search. Comput. Oper. Res. 44, 185\u2013192 (2014)","journal-title":"Comput. Oper. Res."},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.cor.2015.06.009","volume":"64","author":"P San Segundo","year":"2015","unstructured":"San Segundo, P., Nikolaev, A., Batsyn, M.: Infra-chromatic bound for exact maximum clique search. Comput. Oper. Res. 64, 293\u2013303 (2015)","journal-title":"Comput. Oper. Res."},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-11440-3_18","volume-title":"WALCOM: Algorithms and Computation","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. In: Rahman, Md.S, Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191\u2013203. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-11440-3_18"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s10878-012-9592-6","volume":"27","author":"M Batsyn","year":"2014","unstructured":"Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27, 397\u2013416 (2014)","journal-title":"J. Comb. Optim."},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Li, C.-M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: Proceedings of ICTAI, pp. 344\u2013351 (2010)","DOI":"10.1109\/ICTAI.2010.57"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Li, C.-M., Fang, Z., Xu, K.: Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. In: Proceedings of ICTAI, pp. 939\u2013946 (2013)","DOI":"10.1109\/ICTAI.2013.143"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and nonapproximability \u2014 towards tight results. In: 1995 Proceedings of 36th Annual Symposium on Foundations of Computer Science, pp. 422\u2013431. IEEE (1995)","DOI":"10.1109\/SFCS.1995.492573"},{"issue":"1","key":"26_CR17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J Moon","year":"1965","unstructured":"Moon, J., Moser, L.: On cliques in graphs. Isr. J. Math. 3(1), 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"key":"26_CR18","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. Technical report, Computer Science Department, School of Humanities and Sciences, Stanford University, Stanford, CA, USA (1976)"},{"key":"26_CR19","unstructured":"Robson, J.M.: Finding a maximum independent set in time $$ O(2^{{{n \\mathord{\\left\/ {\\vphantom {n 4}} \\right. \\kern-0pt} 4}}} ) $$ . Technical report 1251-01, LaBRI, Universit\u00e9 de Bordeaux I (2001)"},{"key":"26_CR20","unstructured":"Lavnikevich, N.: On the complexity of maximum clique algorithms: usage of coloring heuristics leads to the $$ \\Omega \\left( {2^{{{n \\mathord{\\left\/ {\\vphantom {n 5}} \\right. \\kern-0pt} 5}}} } \\right) $$ algorithm running time lower bound (2013)"},{"issue":"4","key":"26_CR21","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":"26_CR22","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."}],"container-title":["Lecture Notes in Computer Science","Machine Learning, Optimization, and Big Data"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51469-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T21:37:45Z","timestamp":1749850665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51469-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319514680","9783319514697"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51469-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}