{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:47:11Z","timestamp":1725544031307},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114397"},{"type":"electronic","value":"9783642114403"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11440-3_26","type":"book-chapter","created":{"date-parts":[[2010,2,2]],"date-time":"2010-02-02T16:03:36Z","timestamp":1265126616000},"page":"281-292","source":"Crossref","is-referenced-by-count":14,"title":["A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs"],"prefix":"10.1007","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R. Tarjan","year":"1977","unstructured":"Tarjan, R., Trojanowski, A.: Finding a maximum independent set. SIAM J. on Computing\u00a06(3), 537\u2013546 (1977)","journal-title":"SIAM J. on Computing"},{"issue":"9","key":"26_CR2","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1109\/TC.1986.1676847","volume":"35","author":"T. Jian","year":"1986","unstructured":"Jian, T.: An O(20.304n\n                  ) algorithm for solving maximum independent set problem. IEEE Transactions on Computers\u00a035(9), 847\u2013851 (1986)","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"26_CR3","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J. Robson","year":"1986","unstructured":"Robson, J.: Algorithms for maximum independent sets. J. of Algorithms\u00a07(3), 425\u2013440 (1986)","journal-title":"J. of Algorithms"},{"key":"26_CR4","unstructured":"Robson, J.: Finding a maximum independent set in time O(2n\/4). Technical Report 1251-01, LaBRI, Universit\u00e9 Bordeaux I (2001)"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/1109557.1109560","volume-title":"SODA","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(20.288n\n                  ) independent set algorithm. In: SODA, pp. 18\u201325. ACM Press, New York (2006)"},{"key":"26_CR6","first-page":"856","volume-title":"SODA","author":"R. Beigel","year":"1999","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: SODA, pp. 856\u2013857. ACM Press, New York (1999)"},{"issue":"4","key":"26_CR7","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":"2","key":"26_CR8","first-page":"153","volume":"28","author":"M.Y. Xiao","year":"2005","unstructured":"Xiao, M.Y., Chen, J.E., Han, X.L.: Improvement on vertex cover and independent set problems for low-degree graphs. Chinese Journal of Computers\u00a028(2), 153\u2013160 (2005)","journal-title":"Chinese Journal of Computers"},{"key":"26_CR9","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.T.: An O\n                  *(1.0977\n                    n\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)"},{"issue":"5","key":"26_CR10","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. Inf. Process. Lett.\u00a097(5), 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"key":"26_CR11","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":"26_CR12","series-title":"Texts in Algorithmics","first-page":"131","volume-title":"ACiD","author":"I. Razgon","year":"2006","unstructured":"Razgon, I.: A faster solving of the maximum independent set problem for graphs with maximal degree 3. In: Broersma, H., Dantchev, S.S., Johnson, M., Szeider, S. (eds.) ACiD. Texts in Algorithmics, vol.\u00a07, pp. 131\u2013142. King\u2019s College, London (2006)"},{"issue":"2","key":"26_CR13","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. J. of Discrete Algorithms\u00a07(2), 191\u2013212 (2009)","journal-title":"J. of Discrete Algorithms"},{"key":"26_CR14","unstructured":"Chen, J., Kanj, I., Xia, G.: Simplicity is beauty: Improved upper bounds for vertex cover. Technical Report TR05-008, School of CTI, DePaul University (2005)"},{"key":"26_CR15","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithms for max independent set in graphs of small average degree. CoRR abs\/0901.1563 (2009)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11440-3_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:36Z","timestamp":1606185636000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11440-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114397","9783642114403"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11440-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}