{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:54Z","timestamp":1759638594674,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319171418"},{"type":"electronic","value":"9783319171425"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-17142-5_24","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T11:19:29Z","timestamp":1429096769000},"page":"272-283","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Exact Algorithm for Maximum Induced Matching"],"prefix":"10.1007","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Huan","family":"Tan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"issue":"2","key":"24_CR1","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time $$o(1.3289^n)$$. J. Algorithms 54(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discret. Appl. Math. 24, 97\u2013102 (1989)","journal-title":"Discret. Appl. Math."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Chang, M.-S., Hung, L.-J., Miau, C.-A.: An $$O^*(1.4786^n)$$-time algorithm for the maximum induced matching problem. In: Chang, R.-S. et al. (eds.): Advances in Intelligent Systems and Applications, SIST 20, pp. 49\u201358 (2013)","DOI":"10.1007\/978-3-642-35452-6_7"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jda.2004.05.001","volume":"3","author":"W Duckwortha","year":"2005","unstructured":"Duckwortha, W., Manloveb, D.F., Zito, M.: On the approximability of the maximum induced matching problem. J. Discret. Algorithms 3(1), 79\u201391 (2005)","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"24_CR5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293\u2013307 (2008)","journal-title":"Algorithmica"},{"issue":"5","key":"24_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 1\u201332 (2009)","journal-title":"J. ACM"},{"key":"24_CR7","doi-asserted-by":"publisher","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, New York (2010)"},{"key":"24_CR8","doi-asserted-by":"publisher","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. Discret. Appl. Math. 44, 79\u201389 (1993)","journal-title":"Discret. Appl. Math."},{"key":"24_CR9","doi-asserted-by":"publisher","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. Discret. Appl. Math. 101, 157\u2013165 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","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. Discret. Math. 26(4), 1758\u20131780 (2012)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"24_CR11","doi-asserted-by":"publisher","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. Discret. Math. 16(4), 517\u2013523 (2003)","journal-title":"SIAM J. Discret. Math."},{"key":"24_CR12","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 clawfree and p5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327\u2013346 (2003)","journal-title":"Algorithmica"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.dam.2008.07.011","volume":"157","author":"H Mosera","year":"2009","unstructured":"Mosera, H., Sikdar, S.: The parameterized complexity of the induced matching problem. Discret. Appl. Math. 157, 715\u2013727 (2009)","journal-title":"Discret. Appl. Math."},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","volume":"5","author":"Y Orlovicha","year":"2008","unstructured":"Orlovicha, Y., Finkeb, G., Gordonc, V., Zverovichd, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5, 584\u2013593 (2008)","journal-title":"Discret. Optim."},{"issue":"1","key":"24_CR15","doi-asserted-by":"publisher","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-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"24_CR16","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00453-011-9546-x","volume":"64","author":"JM Van Rooij","year":"2012","unstructured":"Van Rooij, J.M., Bodlaender, H.L.: Exact algorithms for edge domination. Algorithmica 64(4), 535\u2013563 (2012)","journal-title":"Algorithmica"},{"issue":"17","key":"24_CR17","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"JM Van Rooij","year":"2011","unstructured":"Van Rooij, J.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discret. Appl. Math. 159(17), 2147\u20132164 (2011)","journal-title":"Discret. Appl. Math."},{"key":"24_CR18","doi-asserted-by":"publisher","unstructured":"Xiao, M., Nagamochi, H.: An improved exact algorithm for undirected feedback vertex set. J.Comb. Optim. (2014). doi:10.1007\/s10878-014-9737-x","DOI":"10.1007\/s10878-014-9737-x"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2014.07.019","volume":"560","author":"M Xiao","year":"2014","unstructured":"Xiao, M., Nagamochi, A.: A refined exact algorithm for edge dominating. Theoret. Comput. Sci. 560, 207\u2013216 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-45030-3_31","volume-title":"Algorithms and Computation","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 328\u2013338. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-17142-5_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:37:42Z","timestamp":1676939862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-17142-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319171418","9783319171425"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-17142-5_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}