{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T21:13:38Z","timestamp":1784236418185,"version":"3.55.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319426334","type":"print"},{"value":"9783319426341","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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_28","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"345-356","source":"Crossref","is-referenced-by-count":9,"title":["On the Power of Simple Reductions for the Maximum Independent Set Problem"],"prefix":"10.1007","author":[{"given":"Darren","family":"Strash","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"issue":"3","key":"28_CR1","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"NF Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, N.F., Fellows, R.M., Langston, A.M., Suters, H.W.: Crown structures for vertex cover kernelization. Theor. Comput. Syst. 41(3), 411\u2013430 (2007)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"28_CR2","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/S0895480191217569","volume":"7","author":"AA Ageev","year":"1994","unstructured":"Ageev, A.A.: On finding critical independent and vertex sets. SIAM J. Discrete Math. 7(2), 293\u2013295 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"Part 1","key":"28_CR3","doi-asserted-by":"crossref","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(Part 1), 211\u2013225 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"28_CR4","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","volume":"18","author":"DV Andrade","year":"2012","unstructured":"Andrade, D.V., Resende, M.G., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525\u2013547 (2012)","journal-title":"J. Heuristics"},{"key":"28_CR5","unstructured":"Batagelj, V., Mrvar, A.: Pajek datasets (2006). http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/"},{"issue":"2","key":"28_CR6","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(2), 397\u2013416 (2014)","journal-title":"J. Comb. Optim."},{"key":"28_CR7","doi-asserted-by":"crossref","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 20th International Conference on World Wide Web (WWW 2011), pp. 587\u2013596. ACM Press (2011)","DOI":"10.1145\/1963405.1963488"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: Proceedings of 13th International Conference on World Wide Web (WWW 2004), pp. 595\u2013601, Manhattan, USA, 2004. ACM Press","DOI":"10.1145\/988672.988752"},{"issue":"1\u20132","key":"28_CR9","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N Bourgeois","year":"2012","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.: Fast algorithms for max independent set. Algorithmica 62(1\u20132), 382\u2013415 (2012)","journal-title":"Algorithmica"},{"key":"28_CR10","series-title":"Springer Optimization and Its Applications","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-0-387-98096-6_12","volume-title":"Optimization","author":"S Butenko","year":"2009","unstructured":"Butenko, S., Pardalos, P., Sergienko, I., Shylo, V., Stetsyuk, P.: Estimating the size of correcting codes using extremal graph problems. In: Pearce, C., Hunt, E. (eds.) Optimization. Springer Optimization and Its Applications, vol. 32, pp. 227\u2013243. Springer, Heidelberg (2009)"},{"issue":"4","key":"28_CR11","doi-asserted-by":"crossref","first-page":"519","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), 519\u2013524 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"28_CR12","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"issue":"5","key":"28_CR13","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":"28_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F Fomin","year":"2010","unstructured":"Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/978-3-642-40450-4_45","volume-title":"Algorithms \u2013 ESA 2013","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., S\u00e1nchez Villaamil, F., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 529\u2013540. Springer, Heidelberg (2013)"},{"key":"28_CR16","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"key":"28_CR17","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":"4","key":"28_CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"28_CR19","doi-asserted-by":"crossref","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 2014, pp. 1749\u20131761. SIAM (2014)","DOI":"10.1137\/1.9781611973402.127"},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"28_CR21","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT : the Koblenz network collection. In: Proceedings of 22nd International Conference on World Wide Web (WWW 2013), WWW 2013 Companion, pp. 1343\u20131350, New York, NY, USA, 2013. ACM","DOI":"10.1145\/2487788.2488173"},{"key":"28_CR22","unstructured":"Larson, C.: A note on critical independence reductions. In: Bulletin of the Institute of Combinatorics and its Applications, vol. 51, pp. 34\u201346 (2007)"},{"key":"28_CR23","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection, June 2014. http:\/\/snap.stanford.edu\/data"},{"key":"28_CR24","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 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013), pp. 939\u2013946, November 2013","DOI":"10.1109\/ICTAI.2013.143"},{"issue":"1","key":"28_CR25","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter, J.: L.E. vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"issue":"3","key":"28_CR26","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."},{"issue":"2","key":"28_CR27","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","volume":"38","author":"P San Segundo","year":"2011","unstructured":"San Segundo, P., Rodrguez-Losada, D., Jimnez, 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":"2","key":"28_CR28","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1287\/ijoc.8.2.87","volume":"8","author":"LA Sanchis","year":"1996","unstructured":"Sanchis, L.A., Jagota, A.: Some experimental and theoretical results on test case generators for the maximum clique problem. INFORMS J. Comput. 8(2), 87\u2013102 (1996)","journal-title":"INFORMS J. Comput."},{"issue":"5","key":"28_CR29","doi-asserted-by":"crossref","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."},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"D535","DOI":"10.1093\/nar\/gkj109","volume":"34","author":"C Stark","year":"2006","unstructured":"Stark, C., Breitkreutz, B., Reguly, T., Boucher, L., Breitkreutz, A., Tyers, M.: Biogrid: a general repository for interaction datasets. Nucleic Acids Res. 34, D535\u2013D539 (2006)","journal-title":"Nucleic Acids Res."},{"key":"28_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"28_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-48481-7_37","volume-title":"Algorithms - ESA\u201999","author":"B Verweij","year":"1999","unstructured":"Verweij, B., Aardal, K.: An optimisation algorithm for maximum independent set with applications in map labelling. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 426\u2013437. Springer, Heidelberg (1999)"},{"key":"28_CR33","doi-asserted-by":"crossref","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."},{"issue":"3","key":"28_CR34","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0403037","volume":"3","author":"C-Q Zhang","year":"1990","unstructured":"Zhang, C.-Q.: Finding critical independent sets and critical vertex subsets are polynomial problems. SIAM J. Discrete Math. 3(3), 431\u2013438 (1990)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:44:15Z","timestamp":1498315455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}