{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:23:53Z","timestamp":1725557033486},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135613"},{"type":"electronic","value":"9783642135620"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13562-0_34","type":"book-chapter","created":{"date-parts":[[2010,5,31]],"date-time":"2010-05-31T05:08:30Z","timestamp":1275282510000},"page":"373-384","source":"Crossref","is-referenced-by-count":6,"title":["Maximum Independent Set in Graphs of Average Degree at Most Three in ${\\mathcal O}(1.08537^n)$"],"prefix":"10.1007","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 Th.","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","reference":[{"key":"34_CR1","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 856\u2013857 (1999)"},{"key":"34_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-79723-4_7","volume-title":"Parameterized and Exact Computation","author":"N. Bourgeois","year":"2008","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th.: An $\\mbox{O}^*(1.0977^{n}$ ) exact algorithm for max independent set in sparse graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 55\u201365. Springer, Heidelberg (2008)"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th., van Rooij, J.M.M.: A bottom-up method and fast algorithms for max independent set. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010 (to appear, 2010)","DOI":"10.1007\/978-3-642-13731-0_7"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th., van Rooij, J.M.M.: Fast algorithms for max independent set in graphs of small average degree. arXiv.org; arXiv:0901.1563v1 [cs.DM] (2009)","DOI":"10.1007\/s00453-010-9460-7"},{"issue":"2","key":"34_CR5","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a041(2), 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"34_CR6","doi-asserted-by":"publisher","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\u00a043(4), 245\u2013273 (2005)","journal-title":"Algorithmica"},{"issue":"4","key":"34_CR7","doi-asserted-by":"publisher","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\u00a035(4), 253\u2013259 (2000)","journal-title":"Networks"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM\u00a056(5) (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"34_CR9","doi-asserted-by":"publisher","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. Information Processing Letters\u00a097, 191\u2013196 (2006)","journal-title":"Information Processing Letters"},{"key":"34_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/11682462_46","volume-title":"LATIN 2006: Theoretical Informatics","author":"M. F\u00fcrer","year":"2006","unstructured":"F\u00fcrer, M.: A faster algorithm for finding maximum independent sets in sparse graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 491\u2013501. Springer, Heidelberg (2006)"},{"issue":"4","key":"34_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR12","unstructured":"Johnson, D.S., Szegedy, M.: What are the least tractable instances of max independent set? In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 927\u2013928 (1999)"},{"key":"34_CR13","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009. LIPIcs, vol.\u00a04, pp. 287\u2013298. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2009)"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1109557.1109559","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006","author":"A. Kojevnikov","year":"2006","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for max-2-sat. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 11\u201317. ACM Press, New York (2006)"},{"key":"34_CR15","unstructured":"Razgon, I.: A faster solving of the maximum independent set problem for graphs with maximal degree 3. In: Algorithms and Complexity in Durham 2006 - Proceedings of the Second ACiD Workshop. Texts in Algorithmics, vol.\u00a07, pp. 131\u2013142. King\u2019s College, London (2006)"},{"issue":"2","key":"34_CR16","doi-asserted-by":"publisher","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. Journal of Discrete Algorithms\u00a07(2), 191\u2013212 (2009)","journal-title":"Journal of Discrete Algorithms"},{"key":"34_CR17","unstructured":"Robson, J.M.: Finding a maximum independent set in time $\\mbox{O}(2^{n\/4})$ . Technical report, LaBRI, Universit\u00e9 Bordeaux I (2001)"},{"key":"34_CR18","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.: Finding a maximum independent set. SIAM Journal on Computing\u00a06, 537\u2013546 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR19","unstructured":"Xiao, M.: New branching rules: Improvements on independent set and vertex cover in sparse graphs. arXiv.org; arXiv:0904.2712v1 [cs.DS] (2009)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13562-0_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T14:09:40Z","timestamp":1559138980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13562-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135613","9783642135620"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13562-0_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}