{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:22Z","timestamp":1759638322205,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662535356"},{"type":"electronic","value":"9783662535363"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53536-3_19","type":"book-chapter","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T12:39:25Z","timestamp":1474979965000},"page":"220-232","source":"Crossref","is-referenced-by-count":1,"title":["Almost Induced Matching: Linear Kernels and Parameterized Algorithms"],"prefix":"10.1007","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Shaowei","family":"Kou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Basavaraju, M., Heggernes, P., Saei, R., Villanger, Y.: Maximal induced matchings in triangle-free graphs. J. Graph Theor. (2015). doi: 10.1002\/jgt.21994","DOI":"10.1002\/jgt.21994"},{"issue":"1\u20133","key":"19_CR2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discrete Appl. Math. 24(1\u20133), 97\u2013102 (1989)","journal-title":"Discrete Appl. Math."},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/978-3-642-29700-7_19","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"J Chen","year":"2012","unstructured":"Chen, J., Fernau, H., Shaw, P., Wang, J., Yang, Z.: Kernels for packing and covering problems. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 199\u2013211. Springer, Heidelberg (2012)"},{"issue":"1","key":"19_CR4","doi-asserted-by":"crossref","first-page":"70","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 3(1), 70\u201391 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"19_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)"},{"key":"19_CR6","unstructured":"Goldberg, A.V., Kaplan, H., Hed, S., Tarjan, R.E.: Minimum cost flows in graphs with unit capacites. In: STACS 2015, LIPIcs 30, Dagstuhl, Germany, pp. 406\u2013419 (2015)"},{"issue":"1\u20133","key":"19_CR7","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Appl. Math. 101(1\u20133), 157\u2013165 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"19_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0166-218X(93)90223-B","volume":"44","author":"MC Golumbic","year":"1993","unstructured":"Golumbic, M.C., Laskar, R.: Irredundancy in circular arc graphs. Discrete Appl. Math. 44(1\u20133), 79\u201389 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"19_CR9","doi-asserted-by":"crossref","first-page":"1758","DOI":"10.1137\/09077850X","volume":"26","author":"S Gupta","year":"2012","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Maximum $$r$$ -regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math. 26(4), 1758\u20131780 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"19_CR10","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1016\/j.jcss.2010.09.001","volume":"77","author":"IA Kanj","year":"2011","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. J. Comput. Syst. Sci. 77(6), 1058\u20131070 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"19_CR11","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/S089548019828371X","volume":"16","author":"CW Ko","year":"2003","unstructured":"Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM J. Discrete Math. 16(4), 517\u2013523 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"19_CR12","doi-asserted-by":"crossref","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 P5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37(4), 327\u2013346 (2003)","journal-title":"Algorithmica"},{"key":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 575\u2013586. Springer, Heidelberg (2008)"},{"issue":"1","key":"19_CR14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jcss.2011.02.001","volume":"78","author":"L Mathieson","year":"2012","unstructured":"Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. Sci. 78(1), 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"19_CR15","doi-asserted-by":"crossref","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. Discrete Appl. Math. 157(4), 715\u2013727 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"19_CR16","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms 7(2), 181\u2013190 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"19_CR17","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","volume":"5","author":"YL Orlovich","year":"2008","unstructured":"Orlovich, Y.L., Finke, G., Gordon, V.S., Zverovich, I.E.: Approximability results for the maximum and minimum maximal induced matching problems. Discrete Optimaization 5(3), 584\u2013593 (2008)","journal-title":"Discrete Optimaization"},{"issue":"3","key":"19_CR18","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.tcs.2005.10.009","volume":"351","author":"E Prieto","year":"2006","unstructured":"Prieto, E., Sloper, C.: Looking at the stars. Theor. Comput. Sci. 351(3), 437\u2013445 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"19_CR19","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completness of some generalizations of the maximum matching problem. Inf. Proc. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Proc. Lett."},{"issue":"5","key":"19_CR20","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.ipl.2009.12.002","volume":"110","author":"J Wang","year":"2010","unstructured":"Wang, J., Ning, D., Feng, Q., Chen, J.: An improved kernelization for $$P_2$$ -packing. Inf. Proc. Lett. 110(5), 188\u2013192 (2010)","journal-title":"Inf. Proc. Lett."},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/978-3-319-17142-5_24","volume-title":"Theory and Applications of Models of Computation","author":"M Xiao","year":"2015","unstructured":"Xiao, M., Tan, H.: An improved exact algorithm for maximum induced matching. In: Jain, R., Jain, S., Stephan, F. (eds.) TAMC 2015. LNCS, vol. 9076, pp. 272\u2013283. Springer, Heidelberg (2015)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Xiao, M., Tan, H.: Exact Algorithms for Maximum Induced Matching (2016, to appear)","DOI":"10.1007\/978-3-319-17142-5_24"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53536-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T22:01:45Z","timestamp":1568412105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53536-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662535356","9783662535363"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53536-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}