{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:07:02Z","timestamp":1742980022747,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_11","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"134-148","source":"Crossref","is-referenced-by-count":1,"title":["Improved Induced Matchings in Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Rok","family":"Erman","sequence":"first","affiliation":[]},{"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[]},{"given":"Matja\u017e","family":"Krnc","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/jgt.1028","volume":"38","author":"N. Alon","year":"2001","unstructured":"Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. J. Graph Theory\u00a038(3), 113\u2013123 (2001)","journal-title":"J. Graph Theory"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1-3","key":"11_CR3","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.disc.2004.05.003","volume":"285","author":"T.C. Biedl","year":"2004","unstructured":"Biedl, T.C., Demaine, E.D., Duncan, C.A., Fleischer, R., Kobourov, S.G.: Tight bounds on maximal and maximum matchings. Discrete Mathematics\u00a0285(1-3), 7\u201315 (2004)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"11_CR4","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1997.0894","volume":"26","author":"Z.-Z. Chen","year":"1998","unstructured":"Chen, Z.-Z.: Efficient approximation schemes for maximization problems on K\n                        3, 3-free graphs. J. Algorithms\u00a026(1), 166\u2013187 (1998)","journal-title":"J. Algorithms"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: A linear algorithm for five-coloring a planar graph. J. Algorithms\u00a02, 317\u2013327 (1981)","journal-title":"J. Algorithms"},{"issue":"6","key":"11_CR6","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM\u00a052(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"11_CR7","first-page":"637","volume-title":"Proc. FOCS 2005","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: Proc. FOCS 2005, pp. 637\u2013646. IEEE Computer Society Press, Los Alamitos (2005)"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jda.2004.05.001","volume":"3","author":"W. Duckworth","year":"2005","unstructured":"Duckworth, W., Manlove, D., Zito, M.: On the approximability of the maximum induced matching problem. J. Discrete Algorithms\u00a03(1), 79\u201391 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"11_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput.\u00a036(2), 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"11_CR10","unstructured":"Kanj, I.A., Pelsmajer, M.J., Xia, G., Schaefer, M.: On the induced matching problem. In: Proc. STACS 2008, pp. 397\u2013408 (2008); Journal version to appear in J. Comput. Sys. Sci."},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/11940128_56","volume-title":"Algorithms and Computation","author":"\u0141. Kowalik","year":"2006","unstructured":"Kowalik, \u0141.: Approximation scheme for lowest outdegree orientation and graph density measures. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 557\u2013566. Springer, Heidelberg (2006)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.dam.2008.07.011","volume":"157","author":"H. Moser","year":"2009","unstructured":"Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem in planar graphs. Discrete Applied Mathematics\u00a0157, 715\u2013727 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR13","series-title":"Texts in Algorithmics","first-page":"107","volume-title":"Proc. ACiD 2006","author":"H. Moser","year":"2006","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. In: Broersma, H., Dantchev, S.S., Johnson, M., Szeider, S. (eds.) Proc. ACiD 2006. Texts in Algorithmics, vol.\u00a07, pp. 107\u2013118. King\u2019s College, London (2006)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"39","author":"C.S.J.A. Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. Journal of the London Mathematical Society\u00a039, 12 (1964)","journal-title":"Journal of the London Mathematical Society"},{"issue":"3","key":"11_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(79)90133-X","volume":"28","author":"T. Nishizeki","year":"1979","unstructured":"Nishizeki, T., Baybars, I.: Lower bounds on the cardinality of the maximum matchings of planar graphs. Discrete Mathematics\u00a028(3), 255\u2013267 (1979)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"L.J. Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett.\u00a015(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"key":"11_CR18","first-page":"253","volume-title":"Proc. STOC 1978","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proc. STOC 1978, pp. 253\u2013264. ACM Press, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T20:26:25Z","timestamp":1676060785000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}