{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:51:50Z","timestamp":1725490310552},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540738138"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73814-5_32","type":"book-chapter","created":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T05:31:44Z","timestamp":1188624704000},"page":"325-336","source":"Crossref","is-referenced-by-count":5,"title":["The Parameterized Complexity of the Induced Matching Problem in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Hannes","family":"Moser","sequence":"first","affiliation":[]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"32_CR1","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.jcss.2004.03.007","volume":"71","author":"J. Alber","year":"2005","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F.A., Stege, U.: A refined search tree technique for dominating set on planar graphs. Journal of Computer and System Sciences\u00a071(4), 385\u2013405 (2005)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"32_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. Journal of the ACM\u00a051(3), 363\u2013384 (2004)","journal-title":"Journal of the ACM"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 613\u2013628. Springer, Heidelberg (2002)"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 1\u201314. Springer, Heidelberg (2006)"},{"issue":"1-3","key":"32_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2003.05.001","volume":"278","author":"K. Cameron","year":"2004","unstructured":"Cameron, K.: Induced matchings in intersection graphs. Discrete Mathematics\u00a0278(1-3), 1\u20139 (2004)","journal-title":"Discrete Mathematics"},{"issue":"1-3","key":"32_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K. Cameron","year":"2003","unstructured":"Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Mathematics\u00a0266(1-3), 133\u2013142 (2003)","journal-title":"Discrete Mathematics"},{"key":"32_CR7","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM Journal on Computing (to appear)"},{"key":"32_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-540-30140-0_19","volume-title":"Algorithms \u2013 ESA 2004","author":"M. Chleb\u00edk","year":"2004","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 192\u2013203. Springer, Heidelberg (2004)"},{"key":"32_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"1","key":"32_CR10","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. Journal of Discrete Algorithms\u00a03(1), 79\u201391 (2005)","journal-title":"Journal of Discrete Algorithms"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1007\/978-3-540-27836-8_50","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 581\u2013592. Springer, Heidelberg (2004)"},{"issue":"1-3","key":"32_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Applied Mathematics\u00a0101(1-3), 157\u2013165 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/11671411_21","volume-title":"Approximation and Online Algorithms","author":"Z. Gotthilf","year":"2006","unstructured":"Gotthilf, Z., Lewenstein, M.: Tighter approximations for maximum induced matchings in regular graphs. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 270\u2013281. Springer, Heidelberg (2006)"},{"issue":"1","key":"32_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"32_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"ICALP 2007","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/11847250_19","volume-title":"Parameterized and Exact Computation","author":"J. Guo","year":"2006","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Fixed-parameter tractability results for full-degree spanning tree and its dual. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 203\u2013214. Springer, Heidelberg (2006)"},{"issue":"4","key":"32_CR17","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/S089548019828371X","volume":"16","author":"C.W. Ko","year":"2003","unstructured":"Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM Journal on Discrete Mathematics\u00a016(4), 517\u2013523 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"32_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00453-003-1035-4","volume":"37","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and P\n                5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica\u00a037(4), 327\u2013346 (2003)","journal-title":"Algorithmica"},{"issue":"4","key":"32_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","volume":"88","author":"V.V. Lozin","year":"2003","unstructured":"Lozin, V.V., Rautenbach, D.: Some results on graphs without long induced paths. Information Processing Letters\u00a088(4), 167\u2013171 (2003)","journal-title":"Information Processing Letters"},{"key":"32_CR20","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. In: Proceedings of ACiD 2006. Texts in Algorithmics, vol.\u00a07, pp. 107\u2013118. College Publications (2006)"},{"key":"32_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"1","key":"32_CR22","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. Information Processing Letters\u00a015(1), 14\u201319 (1982)","journal-title":"Information Processing Letters"},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-46784-X_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Zito","year":"1999","unstructured":"Zito, M.: Induced matchings in regular graphs and trees. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 89\u2013100. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73814-5_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:00:28Z","timestamp":1619517628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73814-5_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540738138"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73814-5_32","relation":{},"subject":[]}}