{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T05:24:22Z","timestamp":1747459462070},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797227"},{"type":"electronic","value":"9783540797234"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-79723-4_7","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T10:22:17Z","timestamp":1210069337000},"page":"55-65","source":"Crossref","is-referenced-by-count":11,"title":["An\u00a0O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs"],"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"}]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Robson, J.M.: Finding a maximum independent set in time\u00a0O(2\n                  n\/4). Technical Report 1251-01, LaBRI, Universit\u00e9 de Bordeaux\u00a0I (2001)"},{"key":"7_CR2","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proc. Symposium on Discrete Algorithms, SODA 1999, pp. 856\u2013857 (1999)"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-540-24587-2_17","volume-title":"Algorithms and Computation","author":"J. Chen","year":"2003","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 148\u2013157. Springer, Heidelberg (2003)"},{"key":"7_CR4","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. Inform. Process. Lett.\u00a097, 191\u2013196 (2006)","journal-title":"Inform. Process. Lett."},{"key":"7_CR5","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)"},{"key":"7_CR6","unstructured":"Razgon, I.: A faster solving of the maximum independent set problem for graphs with maximal degree\u00a03. In: Proc. Algorithms and Complexity in Durham, ACiD 2006, pp. 131\u2013142 (2006)"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. W\u0153ginger","year":"2003","unstructured":"W\u0153ginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"},{"key":"7_CR8","unstructured":"Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: Proc. Symposium on Discrete Algorithms, SODA 2001, pp. 329\u2013337 (2001)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79723-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:26:26Z","timestamp":1558279586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79723-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540797227","9783540797234"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79723-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}