{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T20:46:55Z","timestamp":1781642815684,"version":"3.54.5"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T00:00:00Z","timestamp":1495497600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"DFG","award":["DFG SA 933\/11-1"],"award-info":[{"award-number":["DFG SA 933\/11-1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s10732-017-9337-x","type":"journal-article","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T18:58:55Z","timestamp":1495565935000},"page":"207-229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":46,"title":["Finding near-optimal independent sets at scale"],"prefix":"10.1007","volume":"23","author":[{"given":"Sebastian","family":"Lamm","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,23]]},"reference":[{"key":"9337_CR1","doi-asserted-by":"publisher","unstructured":"Akiba, T., Iwata, Y.: Branch-and-reduce exponential\/FPT algorithms in practice: a case study of vertex cover. Theor. Comput. Sci. 609(Part 1), 211\u2013225 (2016). doi: 10.1016\/j.tcs.2015.09.023","DOI":"10.1016\/j.tcs.2015.09.023"},{"issue":"4","key":"9337_CR2","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). doi: 10.1007\/s10732-012-9196-4","journal-title":"J. Heuristics"},{"key":"9337_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e4ck, T., Khuri, S.: An evolutionary heuristic for the maximum independent set problem. In: Proceedings of the 1st IEEE Conference on Evolutionary Computation, pp. 531\u2013535. IEEE (1994)","DOI":"10.1109\/ICEC.1994.350004"},{"key":"9337_CR4","doi-asserted-by":"crossref","unstructured":"B\u00e4ck, T.: Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Ph.D. thesis (1996)","DOI":"10.1093\/oso\/9780195099713.001.0001"},{"key":"9337_CR5","doi-asserted-by":"publisher","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, New York (2014). doi: 10.1007\/978-1-4614-6170-8_23","DOI":"10.1007\/978-1-4614-6170-8_23"},{"issue":"2","key":"9337_CR6","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). doi: 10.1007\/s10878-012-9592-6","journal-title":"J. Comb. Optim."},{"issue":"4","key":"9337_CR7","doi-asserted-by":"crossref","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"},{"key":"9337_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: Proceedings of the 13th International World Wide Web Conference (WWW 2004), Manhattan, USA, pp. 595\u2013601. ACM Press (2004)","DOI":"10.1145\/988672.988752"},{"key":"9337_CR9","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1145\/1963405.1963488","volume-title":"Proceedings of the 20th International Conference on World Wide Web","author":"P Boldi","year":"2011","unstructured":"Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M.P., Bertino, E., Kumar, R. (eds.) Proceedings of the 20th International Conference on World Wide Web, pp. 587\u2013596. ACM Press, New York (2011)"},{"key":"9337_CR10","doi-asserted-by":"publisher","unstructured":"Borisovsky, P.A., Zavolovskaya, M.S.: Experimental comparison of two evolutionary algorithms for the independent set problem. In: Cagnoni, S., Johnson C.G., Cardalda, J.J.R., Marchiori, E., Corne, D.W., Meyer, J-A., Gottlieb, J., Middendorf, M., Guillot, A., Raidl, G.R., Hart, E., (eds.) Applications of Evolutionary Computing: EvoWorkshops 2003: EvoBIO, EvoCOP, EvoIASP, EvoMUSART, EvoROB, and EvoSTIM, Essex, UK, April 14\u201316, 2003, pp. 154\u2013164. Springer, Berlin, Heidelberg (2003). doi: 10.1007\/3-540-36605-9_15","DOI":"10.1007\/3-540-36605-9_15"},{"issue":"1\u20132","key":"9337_CR11","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). doi: 10.1007\/s00453-010-9460-7","journal-title":"Algorithmica"},{"key":"9337_CR12","doi-asserted-by":"publisher","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 2002 ACM Symposium on Applied Computing, SAC \u201902, pp. 542\u2013546. ACM, New York, NY, USA. doi: 10.1145\/508791.508897 (2002)","DOI":"10.1145\/508791.508897"},{"issue":"4","key":"9337_CR13","doi-asserted-by":"publisher","first-page":"519524","DOI":"10.1016\/j.orl.2006.07.004","volume":"35","author":"S Butenko","year":"2007","unstructured":"Butenko, S., Trukhanov, S.: Using critical sets to solve the maximum independent set problem. Oper. Res. Lett. 35(4), 519524 (2007). doi: 10.1016\/j.orl.2006.07.004","journal-title":"Oper. Res. Lett."},{"key":"9337_CR14","unstructured":"Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1:1\u20131:25 (2011). ISSN 0098-3500. http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices"},{"key":"9337_CR15","isbn-type":"print","volume-title":"Evolutionary Computation: A Unified Approach","author":"KA Jong De","year":"2006","unstructured":"De Jong, K.A.: Evolutionary Computation: A Unified Approach. MIT Press, Cambridge (2006). ISBN 0-262-04194-4","ISBN":"https:\/\/id.crossref.org\/isbn\/0262041944"},{"key":"9337_CR16","doi-asserted-by":"publisher","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: Design, Analysis, and Simulation, Vol 5515 of LNCS State-of-the-Art Survey, pp. 117\u2013139. Springer, Berlin, Heidelberg (2009). doi: 10.1007\/978-3-642-02094-0_7","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"9337_CR17","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/074","volume-title":"The Shortest Path Problem: 9th DIMACS Implementation Challenge","author":"C Demetrescu","year":"2009","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: The Shortest Path Problem: 9th DIMACS Implementation Challenge, vol. 74. AMS, Providence (2009)"},{"issue":"5","key":"9337_CR18","doi-asserted-by":"crossref","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":"9337_CR19","doi-asserted-by":"crossref","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, New York (2010)"},{"issue":"2","key":"9337_CR20","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1021\/ci990262o","volume":"40","author":"EJ Gardiner","year":"2000","unstructured":"Gardiner, E.J., Willett, P., Artymiuk, P.J.: Graph-theoretic techniques for macromolecular docking. J. Chem. Inf. Comput. Sci. 40(2), 273\u2013279 (2000). doi: 10.1021\/ci990262o","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"9337_CR21","unstructured":"Garey, M.R.: Johnson, David S: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"9337_CR22","doi-asserted-by":"publisher","unstructured":"Gemsa, A., N\u00f6llenburg, M., Rutter, I.: Evaluation of labeling strategies for rotating maps. In: Experimental Algorithms, vol. 8504 of LNCS, pp. 235\u2013246. Springer (2014). doi: 10.1007\/978-3-319-07959-2_20","DOI":"10.1007\/978-3-319-07959-2_20"},{"key":"9337_CR23","unstructured":"Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co., Inc, Boston (1989)"},{"issue":"2","key":"9337_CR24","doi-asserted-by":"crossref","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., Combining, C.: 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":"9337_CR25","doi-asserted-by":"crossref","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":"9337_CR26","doi-asserted-by":"crossref","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":"9337_CR27","doi-asserted-by":"crossref","unstructured":"Harary, F., Ross, I.C.: A procedure for clique detection using the group matrix. Sociometry 20(3), 205\u2013215 (1957). http:\/\/www.jstor.org\/stable\/2785673","DOI":"10.2307\/2785673"},{"key":"9337_CR28","unstructured":"Iwata, Y., Oka, K., Yoshida, Y.: Linear-time FPT algorithms via network flow. In: Proceedings of 25th ACM-SIAM Symposium on Discrete Algorithms, SODA \u201914, pp. 1749\u20131761. SIAM (2014). ISBN 978-1-611973-38-9. http:\/\/dl.acm.org\/citation.cfm?id=2634074.2634201"},{"issue":"5","key":"9337_CR29","doi-asserted-by":"crossref","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. Inf. Process. Lett. 95(5), 503\u2013511 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9337_CR30","doi-asserted-by":"publisher","unstructured":"Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) Experimental Algorithms, of LNCS, vol. 6049, pp. 83\u201393. Springer, Berlin (2010). doi: 10.1007\/978-3-642-13193-6_8","DOI":"10.1007\/978-3-642-13193-6_8"},{"key":"9337_CR31","doi-asserted-by":"crossref","unstructured":"Lamm, S., Sanders, P., Schulz, C.: Graph partitioning for independent sets. In: Proceedings of the 14th International Symposium on Experimental Algorithms (SEA\u201915), vol. 8504, pp. 68\u201381. Springer (2015). ISBN 978-3-642-30849-9","DOI":"10.1007\/978-3-319-20086-6_6"},{"key":"9337_CR32","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 Expermiments, ALENEX\u201916 (2016)","DOI":"10.1137\/1.9781611974317.12"},{"key":"9337_CR33","doi-asserted-by":"publisher","unstructured":"Li, C., Fang, Z., Xu, K.: Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In: Proceedings of 25th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 939\u2013946 (2013). doi: 10.1109\/ICTAI.2013.143","DOI":"10.1109\/ICTAI.2013.143"},{"issue":"13","key":"9337_CR34","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). doi: 10.14778\/2831360.2831366","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"9337_CR35","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1162\/evco.1996.4.2.113","volume":"4","author":"BL Miller","year":"1996","unstructured":"Miller, B.L., Goldberg, D.E.: Genetic algorithms, tournament selection, and the effects of noise. Evolut. Comput. 4(2), 113\u2013131 (1996)","journal-title":"Evolut. Comput."},{"issue":"1","key":"9337_CR36","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975). doi: 10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"9337_CR37","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1613\/jair.1815","volume":"25","author":"WJ Pullan","year":"2006","unstructured":"Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Intell. Res. (JAIR) 25, 159\u2013185 (2006)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"2","key":"9337_CR38","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., Agust\u00edn, J.: 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","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"9337_CR39","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). doi: 10.1007\/s11590-011-0431-y","journal-title":"Optim. Lett."},{"key":"9337_CR40","doi-asserted-by":"publisher","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). doi: 10.1145\/1409060.1409097","DOI":"10.1145\/1409060.1409097"},{"key":"9337_CR41","unstructured":"Sanders, P., Schulz, C.: KaHIP: Karlsruhe high qualtity partitioning homepage. http:\/\/algo2.iti.kit.edu\/documents\/kahip\/index.html"},{"issue":"2","key":"9337_CR42","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1023\/B:JOGO.0000042115.44455.f3","volume":"29","author":"AJ Soper","year":"2004","unstructured":"Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph-partitioning. J. Glob. Optim. 29(2), 225\u2013241 (2004)","journal-title":"J. Glob. Optim."},{"issue":"3","key":"9337_CR43","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). doi: 10.1137\/0206038","journal-title":"SIAM J. Comput."},{"key":"9337_CR44","doi-asserted-by":"publisher","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: Saidur Rahman, M.D., Fujita, S. (eds.) WALCOM: Algorithms and Computation of LNCS, vol. 5942, pp. 191\u2013203. Springer, Berlin (2010). doi: 10.1007\/978-3-642-11440-3_18","DOI":"10.1007\/978-3-642-11440-3_18"},{"issue":"3","key":"9337_CR45","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu, Q., Hao, J.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693\u2013709 (2015). doi: 10.1016\/j.ejor.2014.09.064","journal-title":"Eur. J. Oper. Res."},{"key":"9337_CR46","doi-asserted-by":"publisher","unstructured":"Xiang, J., Guo, C., Aboulnaga, A.: Scalable maximum clique computation using mapreduce. In: Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 74\u201385 (2013). doi: 10.1109\/ICDE.2013.6544815","DOI":"10.1109\/ICDE.2013.6544815"},{"key":"9337_CR47","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 (2013a). doi: 10.1016\/j.tcs.2012.09.022","journal-title":"Theor. Comput. Sci."},{"key":"9337_CR48","doi-asserted-by":"crossref","unstructured":"Xiao, M., Nagamochi, H.: Exact Algorithms for Maximum Independent Set. arXiv:1312.6260 (2013b)","DOI":"10.1007\/978-3-642-45030-3_31"},{"key":"9337_CR49","doi-asserted-by":"crossref","unstructured":"Zaki, M.J., Parthasarathy, S., Ogihara, M., Li, W.: New algorithms for fast discovery of association rules. In: Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, pp. 283\u2013286. AAAI Press (1997)","DOI":"10.1007\/978-1-4615-5669-5_1"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-017-9337-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-017-9337-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-017-9337-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T20:37:25Z","timestamp":1659040645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-017-9337-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,23]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9337"],"URL":"https:\/\/doi.org\/10.1007\/s10732-017-9337-x","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,23]]}}}