{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:52:49Z","timestamp":1725583969541},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387555"},{"type":"electronic","value":"9783642387562"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38756-2_10","type":"book-chapter","created":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T00:43:48Z","timestamp":1369097028000},"page":"72-83","source":"Crossref","is-referenced-by-count":3,"title":["An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs"],"prefix":"10.1007","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"10_CR1","doi-asserted-by":"publisher","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.M.: Fast algorithms for max independent set. Algorithmica\u00a062(1-2), 382\u2013415 (2012)","journal-title":"Algorithmica"},{"issue":"40-42","key":"10_CR2","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"key":"10_CR3","unstructured":"Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: SODA, pp. 781\u2013790. ACM Press (2004)"},{"issue":"5","key":"10_CR4","doi-asserted-by":"publisher","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. ACM\u00a056(5), 1\u201332 (2009)","journal-title":"J. ACM"},{"issue":"5","key":"10_CR5","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":"10_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"10_CR7","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":"9","key":"10_CR8","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"},{"key":"10_CR9","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Kannan, R., Kumar, K.N. (eds.) FSTTCS 2009, Dagstuhl, Germany. LIPIcs, vol.\u00a04, pp. 287\u2013298 (2009)"},{"issue":"2","key":"10_CR10","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"},{"issue":"3","key":"10_CR11","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"},{"issue":"3","key":"10_CR12","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"},{"key":"10_CR13","unstructured":"West, D.: Introduction to Graph Theory. Prentice Hall (1996)"},{"issue":"2","key":"10_CR14","first-page":"153","volume":"28","author":"M. Xiao","year":"2005","unstructured":"Xiao, M., Chen, J.E., Han, X.L.: Improvement on vertex cover and independent set problems for low-degree graphs. Chinese J. of Computers\u00a028(2), 153\u2013160 (2005)","journal-title":"Chinese J. of Computers"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-642-11440-3_26","volume-title":"WALCOM: Algorithms and Computation","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: A simple and fast algorithm for maximum independent set in 3-degree graphs. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.\u00a05942, pp. 281\u2013292. Springer, Heidelberg (2010)"},{"key":"10_CR16","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0469, 92\u2013104 (2013)","journal-title":"Theoretical Computer Science"},{"key":"10_CR17","unstructured":"Xiao, M., Nagamochi, H.: A refined algorithm for maximum independent set in degree-4 graphs. Technical report 2013-002, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University (2013), \n                    \n                      http:\/\/www.amp.i.kyoto-u.ac.jp\/tecrep\/abst\/2013\/2013-002.html"},{"key":"10_CR18","unstructured":"Xiao, M., Nagamochi, H.: An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs. Technical report 2013-003, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University (2013), \n                    \n                      http:\/\/www.amp.i.kyoto-u.ac.jp\/tecrep\/abst\/2013\/2013-003.html"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38756-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T03:13:32Z","timestamp":1557717212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38756-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387555","9783642387562"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38756-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}