{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T22:41:38Z","timestamp":1778539298223,"version":"3.51.4"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319388502","type":"print"},{"value":"9783319388519","type":"electronic"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_9","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:33:54Z","timestamp":1464708834000},"page":"118-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Accelerating Local Search for the Maximum Independent Set Problem"],"prefix":"10.1007","author":[{"given":"Jakob","family":"Dahlum","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Lamm","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"N Faisal Abu-Khzam","year":"2007","unstructured":"Faisal Abu-Khzam, N., Michael Fellows, R., Michael Langston, A., Suters, H.W.: Crown structures for vertex cover kernelization. Theor. Comput. Syst. 41(3), 411\u2013430 (2007)","journal-title":"Theor. Comput. Syst."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","volume":"609","author":"T Akiba","year":"2016","unstructured":"Akiba, T., Iwata, Y.: Branch-and-reduce exponential\/FPT algorithms in practice: A case study of vertex cover. Theor. Comput. Sci. 609, 211\u2013225 (2016). Part 1","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","volume":"18","author":"DV Andrade","year":"2012","unstructured":"Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525\u2013547 (2012)","journal-title":"J. Heuristics"},{"key":"9_CR4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-1-4614-6170-8_23","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"DA Bader","year":"2014","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.: Benchmarking for Graph Clustering and Partitioning. In: Alhajj, R., Rokne, J. (eds.) Encyclopedia of Social Network Analysis and Mining, pp. 73\u201382. Springer, Heidelberg (2014)"},{"issue":"2","key":"9_CR5","doi-asserted-by":"publisher","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(2), 397\u2013416 (2014)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"9_CR6","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s004530010074","volume":"29","author":"R Battiti","year":"2001","unstructured":"Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem. Algorithmica 29(4), 610\u2013637 (2001)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"9_CR7","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N Bourgeois","year":"2012","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V., van Rooij, J.M.: Fast algorithms for max independent set. Algorithmica 62(1\u20132), 382\u2013415 (2012)","journal-title":"Algorithmica"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Butenko, S., Pardalos, P., Sergienko, I., Shylo, V., Stetsyuk, P.: Finding maximum independent sets in graphs arising from coding theory. In: Proceedings of the ACM Symposium on Applied Computing (SAC 2002), pp. 542\u2013546. ACM (2002)","DOI":"10.1145\/508791.508897"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-02094-0_7","volume-title":"Algorithmics of Large and Complex Networks","author":"D Delling","year":"2009","unstructured":"Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. LNCS, vol. 5515, pp. 117\u2013139. Springer, Heidelberg (2009)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: The Shortest Path Problem: 9th DIMACS Implementation Challenge, vol. 74. AMS (2009)","DOI":"10.1090\/dimacs\/074"},{"issue":"5","key":"9_CR11","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1287\/opre.42.5.860","volume":"42","author":"TA Feo","year":"1994","unstructured":"Feo, T.A., Resende, M.G.C., Smith, S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42(5), 860\u2013878 (1994)","journal-title":"Oper. Res."},{"key":"9_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)"},{"key":"9_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of np-completeness. In: Freeman, W.H. (1979)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-319-07959-2_20","volume-title":"Experimental Algorithms","author":"A Gemsa","year":"2014","unstructured":"Gemsa, A., N\u00f6llenburg, M., Rutter, I.: Evaluation of labeling strategies for rotating maps. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 235\u2013246. Springer, Heidelberg (2014)"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1023\/B:HEUR.0000026264.51747.7f","volume":"10","author":"A Grosso","year":"2004","unstructured":"Grosso, A., Locatelli, M., Della, F.C.: Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. J. Heuristics 10(2), 135\u2013152 (2004)","journal-title":"J. Heuristics"},{"issue":"6","key":"9_CR16","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s10732-007-9055-x","volume":"14","author":"A Grosso","year":"2008","unstructured":"Grosso, A., Locatelli, M., Pullan, W.: Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14(6), 587\u2013612 (2008)","journal-title":"J. Heuristics"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.dam.2003.09.012","volume":"145","author":"P Hansen","year":"2004","unstructured":"Hansen, P., Mladenovi\u0107, N., Uro\u0161evi\u0107, D.: Variable neighborhood search for the maximum clique. Discrete Appl. Math. 145(1), 117\u2013125 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K., Yoshida, Y.: Linear-time FPT algorithms via network flow. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 1749\u20131761. SIAM (2014)","DOI":"10.1137\/1.9781611973402.127"},{"issue":"5","key":"9_CR19","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.ipl.2005.05.010","volume":"95","author":"K Katayama","year":"2005","unstructured":"Katayama, K., Hamamoto, A., Narihisa, H.: An effective local search for the maximum clique problem. Inform. Process. Lett. 95(5), 503\u2013511 (2005)","journal-title":"Inform. Process. Lett."},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-13193-6_8","volume-title":"Experimental Algorithms","author":"T Kieritz","year":"2010","unstructured":"Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 83\u201393. Springer, Heidelberg (2010)"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT: The Koblenz network collection. In: Proceedings of the International Conference on World Wide Web Companion (WWW 13), pp. 1343\u20131350 (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"9_CR22","unstructured":"University of Milano Laboratory of Web Algorithms. Datasets"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-20086-6_6","volume-title":"Experimental Algorithms","author":"S Lamm","year":"2015","unstructured":"Lamm, S., Sanders, P., Schulz, C.: Graph partitioning for independent sets. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 68\u201381. Springer, Heidelberg (2015)"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Lamm, S., Sanders, P., Schulz, C., Strash, D., Werneck, R.F.: Finding near-optimal independent sets at scale. In: Proceedings of the 18th Workshop on Algorithm Engineering and Experiments (ALENEX 2016), pp. 138\u2013150 (2016)","DOI":"10.1137\/1.9781611974317.12"},{"issue":"13","key":"9_CR25","doi-asserted-by":"publisher","first-page":"2122","DOI":"10.14778\/2831360.2831366","volume":"8","author":"Y Liu","year":"2015","unstructured":"Liu, Y., Lu, J., Yang, H., Xiao, X., Wei, Z.: Towards maximum independent sets on massive graphs. Proc. VLDB Endow. 8(13), 2122\u20132133 (2015)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: Structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"9_CR27","first-page":"159","volume":"25","author":"WJ Pullan","year":"2006","unstructured":"Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique. J. Arti. Int. Res. 25, 159\u2013185 (2006)","journal-title":"J. Arti. Int. Res."},{"issue":"3","key":"9_CR28","doi-asserted-by":"publisher","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."},{"issue":"5","key":"9_CR29","doi-asserted-by":"publisher","first-page":"144:1","DOI":"10.1145\/1409060.1409097","volume":"27","author":"PV Sander","year":"2008","unstructured":"Sander, P.V., Nehab, D., Chlamtac, E., Hoppe, H.: Efficient traversal of mesh edges using adjacency primitives. ACM Trans. Graph. 27(5), 144:1\u2013144:9 (2008)","journal-title":"ACM Trans. Graph."},{"issue":"2","key":"9_CR30","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","volume":"38","author":"P San Segundo","year":"2011","unstructured":"San Segundo, P., Rodr\u00edguez-Losada, D., Jim\u00e9nez, D.: 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":"9_CR31","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"RE Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6(3), 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"key":"9_CR32","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, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191\u2013203. Springer, Heidelberg (2010)"},{"key":"9_CR33","doi-asserted-by":"crossref","unstructured":"Xiang, J., Guo, C., Aboulnaga, A.: Scalable maximum clique computation using mapreduce. In: Proceedings of the IEEE 29th International Conference on Data Engineering (ICDE 2013), pp. 74\u201385, April 2013","DOI":"10.1109\/ICDE.2013.6544815"},{"key":"9_CR34","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2012.09.022","volume":"469","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Nagamochi, H.: Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theor. Comput. Sci. 469, 92\u2013104 (2013)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T20:05:41Z","timestamp":1748981141000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}