{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:07Z","timestamp":1777539967645,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,10,19]],"date-time":"2010-10-19T00:00:00Z","timestamp":1287446400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9460-7","type":"journal-article","created":{"date-parts":[[2010,10,18]],"date-time":"2010-10-18T17:02:06Z","timestamp":1287421326000},"page":"382-415","source":"Crossref","is-referenced-by-count":49,"title":["Fast Algorithms for max independent set"],"prefix":"10.1007","volume":"62","author":[{"given":"Nicolas","family":"Bourgeois","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Escoffier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis T.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johan M. M.","family":"van Rooij","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,10,19]]},"reference":[{"key":"9460_CR1","first-page":"856","volume-title":"Proc. Symposium on Discrete Algorithms, SODA\u201999","author":"R. Beigel","year":"1999","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proc. Symposium on Discrete Algorithms, SODA\u201999, pp. 856\u2013857 (1999)"},{"key":"9460_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-3-540-79723-4_7","volume-title":"Proc. International Workshop on Exact and Parameterized Computation, IWPEC\u201908","author":"N. Bourgeois","year":"2008","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th.: An O \u2217(1.0977 n ) exact algorithm for max independent set in sparse graphs. In: Grohe, M., Niedermeier, R. (eds.) Proc. International Workshop on Exact and Parameterized Computation, IWPEC\u201908. Lecture Notes in Computer Science, vol. 5018, pp. 55\u201365. Springer, Berlin (2008)"},{"key":"9460_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/978-3-642-13562-0_34","volume-title":"Proc. Conference on Theory and Applications of Models of Computation, TAMC\u201910","author":"N. Bourgeois","year":"2010","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th., Van Rooij, J.M.M: Maximum independent set in graphs of average degree at most three in O(1.08537 n ). In: Kratochv\u00edl, J., Li, A., Fiala, J., Kolman, P. (eds.) Proc. Conference on Theory and Applications of Models of Computation, TAMC\u201910. Lecture Notes in Computer Science, vol. 6108, pp. 373\u2013384. Springer, Berlin (2010)"},{"issue":"4","key":"9460_CR4","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K","volume":"35","author":"J. Chen","year":"2000","unstructured":"Chen, J., Liu, L., Jia, W.: Improvement on vertex cover for low-degree graphs. Networks 35(4), 253\u2013259 (2000)","journal-title":"Networks"},{"issue":"4","key":"9460_CR5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J. Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43(4), 245\u2013273 (2005)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"9460_CR6","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formul\u00e6. Theor. Comput. Sci. 332(1\u20133), 265\u2013291 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9460_CR7","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f8ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9460_CR8","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"9460_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. Assoc. Comput. Mach. 56(5), 1\u201332 (2009)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9460_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/11682462_46","volume-title":"Proc. Latin American Symposium on Theoretical Informatics, LATIN\u201906","author":"M. F\u00fcrer","year":"2006","unstructured":"F\u00fcrer, M.: A faster algorithm for finding maximum independent sets in sparse graphs. In: Corea, J.R., Hevia, A., Kiwi, M. (eds.) Proc. Latin American Symposium on Theoretical Informatics, LATIN\u201906. Lecture Notes in Computer Science, vol. 3887, pp. 491\u2013501. Springer, Berlin (2006)"},{"key":"9460_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-540-72870-2_5","volume-title":"Proc. Algorithmic Aspects in Information and Management, AAIM\u201907","author":"M. F\u00fcrer","year":"2007","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. In: Kao, M.-Y., Li, X.-Y. (eds.) Proc. Algorithmic Aspects in Information and Management, AAIM\u201907. Lecture Notes in Computer Science, vol. 4508, pp. 47\u201357. Springer, Berlin (2007)"},{"key":"9460_CR12","first-page":"431","volume-title":"Graph Theory, Combinatorics and Algorithms. Proc. 7th Quadrennial International Conference on the Theory and Application of Graphs","author":"M.K. Goldberg","year":"1992","unstructured":"Goldberg, M.K., Spencer, T.H., Berque, D.A.: A low-exponential algorithm for counting vertex covers. In: Graph Theory, Combinatorics and Algorithms. Proc. 7th Quadrennial International Conference on the Theory and Application of Graphs, vol. 1, pp. 431\u2013444. Wiley, New York (1992)"},{"key":"9460_CR13","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Kannan, R., Narayan Kumar, K. (eds.) Proc. Foundations of Software Technology and Theoretical Computer Science, FSTTCS\u201909. LIPIcs, vol. 4, pp.\u00a0287\u2013298. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2009)"},{"key":"9460_CR14","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1109557.1109559","volume-title":"Proc. Symposium on Discrete Algorithms, SODA\u201906","author":"A. Kojevnikov","year":"2006","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for max-2-sat. In: Proc. Symposium on Discrete Algorithms, SODA\u201906, pp. 11\u201317 (2006)"},{"key":"9460_CR15","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.jda.2008.09.004","volume":"7","author":"I. Razgon","year":"2009","unstructured":"Razgon, I.: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discrete Algorithms 7, 191\u2013212 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"9460_CR16","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"9460_CR17","unstructured":"Robson, J.M.: Finding a maximum independent set in time O(2 n\/4). Technical Report 1251-01, LaBRI, Universit\u00e9 de Bordeaux\u00a0I (2001)"},{"key":"9460_CR18","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer, a\u00a0faster exact algorithm for dominating set. In: Albers, S., Weil, P. (eds.) Proc. International Symposium on Theoretical Aspects of Computer Science, STACS\u201908, pp.\u00a0657\u2013668. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany (2008)"},{"key":"9460_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/978-3-540-79723-4_19","volume-title":"Proc. Parameterized and Exact Computation, Third International Workshop, IWPEC\u201908","author":"M. Wahlstr\u00f6m","year":"2008","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2sat instances. In: Grohe, M., Niedermeier, R. (eds.) Proc. Parameterized and Exact Computation, Third International Workshop, IWPEC\u201908. Lecture Notes in Computer Science, vol. 5018, pp. 202\u2013213. Springer, Berlin (2008)"},{"key":"9460_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization\u2014Eureka! You shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a\u00a0survey. In: Juenger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization\u2014Eureka! You shrink! Lecture Notes in Computer Science, vol. 2570, pp. 185\u2013207. Springer, Berlin (2003)"},{"key":"9460_CR21","unstructured":"Xiao, M.: New branching rules: improvements on independent set and vertex cover in sparse graphs. CoRR (2009). arXiv:0904.2712"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9460-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9460-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9460-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:06Z","timestamp":1559123106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9460-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,19]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9460"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9460-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,19]]}}}