{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:50:09Z","timestamp":1767340209680},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T00:00:00Z","timestamp":1413936000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s11590-014-0813-z","type":"journal-article","created":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T03:49:40Z","timestamp":1413949780000},"page":"981-998","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Moderately exponential time algorithms for the maximum induced matching problem"],"prefix":"10.1007","volume":"9","author":[{"given":"Maw-Shang","family":"Chang","sequence":"first","affiliation":[]},{"given":"Li-Hsuan","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,22]]},"reference":[{"key":"813_CR1","doi-asserted-by":"crossref","unstructured":"Balakrishnan, H., Barrett, C.L., Anil Kumar, V.S., Marathe, M.V., Thite., S.: The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE J. Select. Areas Commun. 22 (6), 1069\u20131079 (2004)","DOI":"10.1109\/JSAC.2004.830909"},{"key":"813_CR2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.jda.2011.03.002","volume":"9","author":"D Binkele-Raible","year":"2011","unstructured":"Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the $$2^n$$ 2 n -barrier for irredundance: two lines of attack. J. Discret. Algorithms 9, 214\u2013230 (2011)","journal-title":"J. Discret. Algorithms"},{"key":"813_CR3","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, VTh: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159, 1954\u20131970 (2011)","journal-title":"Discret. Appl. Math."},{"key":"813_CR4","unstructured":"Cardoso, D.M., Kaminski, M., Lozin, V.: Maximum $$k$$ k -regular induced subgraphs, Rutcor Research Report (RRR) 3 (2006)"},{"key":"813_CR5","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 matching. Discret. Appl. Math. 24, 97\u2013102 (1989)","journal-title":"Discret. Appl. Math."},{"key":"813_CR6","doi-asserted-by":"crossref","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. Discret. Math. 266, 133\u2013142 (2003)","journal-title":"Discret. Math."},{"key":"813_CR7","doi-asserted-by":"crossref","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. Discret. Math. 278, 1\u20139 (2004)","journal-title":"Discret. Math."},{"key":"813_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In Proceedings of FOCS 2013, pp. 370\u2013379","DOI":"10.1109\/FOCS.2013.47"},{"key":"813_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"J-M Chang","year":"2004","unstructured":"Chang, J.-M.: Induced matching in asteroidal triple-free graphs. Discret. Appl. Math. 132, 67\u201378 (2004)","journal-title":"Discret. Appl. Math."},{"key":"813_CR10","first-page":"49","volume-title":"Proceedings of ICS 2012: algorithms and bioinformatics workshop, advances in intelligent systems and application, SIST 20","author":"M-S Chang","year":"2013","unstructured":"Chang, M.-S., Hung, L.-J., Miau, C.-A.: An $$O^{\\ast }(1.4786^n)$$ O * ( 1 . 4786 n ) -time algorithm for the maximum induced matching problem. In: Chang, R.S., Jain, L.C., Peng, S.-L. (eds.) Proceedings of ICS 2012: algorithms and bioinformatics workshop, advances in intelligent systems and application, SIST 20, pp. 49\u201358. Springer, Berlin (2013)"},{"key":"813_CR11","doi-asserted-by":"crossref","first-page":"2387","DOI":"10.1016\/j.cor.2013.04.009","volume":"40","author":"IT Christou","year":"2013","unstructured":"Christou, I.T., Vassilaras, S.: A parallel hybrid greedy branch and bound scheme for the maximum distace-2 matching problem. Comput. Operat. Res. 40, 2387\u20132397 (2013)","journal-title":"Comput. Operat. Res."},{"key":"813_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, JO.: Irredundant set faster than $$O(2^n)$$ O ( 2 n ) . In: Proceedings of CIAC 2010, LNCS 6078, pp. 288\u2013298 (2010)","DOI":"10.1007\/978-3-642-13073-1_26"},{"key":"813_CR13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.tcs.2013.01.027","volume":"478","author":"K Dabrowski","year":"2013","unstructured":"Dabrowski, K., Demange, M., Lozin, V.V.: New results on maximum induced matchings in bipartite graphs and beyond. Theor. Comput. Sci. 478, 33\u201340 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"813_CR14","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jda.2004.05.001","volume":"3","author":"W Duckworth","year":"2005","unstructured":"Duckworth, W., Manlove, D.F., Zito, M.: On the approximability of the maximum induced matching problem. J. Discret. Algorithms 3, 79\u201391 (2005)","journal-title":"J. Discret. Algorithms"},{"key":"813_CR15","doi-asserted-by":"crossref","first-page":"1994","DOI":"10.1016\/j.dam.2010.08.026","volume":"158","author":"R Erman","year":"2010","unstructured":"Erman, R., Kowalik, \u0141., Krnc, M., Wale\u0144, T.: Improved induced matching in sparse graphs. Discret. Appl. Math. 158, 1994\u20132003 (2010)","journal-title":"Discret. Appl. Math."},{"key":"813_CR16","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, Berlin (2010)"},{"key":"813_CR17","first-page":"239","volume":"89","author":"G Fricke","year":"1992","unstructured":"Fricke, G., Laskar, R.: String matching in trees. Congr. Numer. 89, 239\u2013243 (1992)","journal-title":"Congr. Numer."},{"key":"813_CR18","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$$ r -regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discret. Math. 26, 1758\u20131780 (2012)","journal-title":"SIAM J. Discret. Math."},{"key":"813_CR19","first-page":"27","volume":"25","author":"K Hosono","year":"1990","unstructured":"Hosono, K.: Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25, 27\u201329 (1990)","journal-title":"Proc. Fac. Sci. Tokai Univ."},{"key":"813_CR20","doi-asserted-by":"crossref","first-page":"1383","DOI":"10.1137\/100808824","volume":"26","author":"RJ Kang","year":"2012","unstructured":"Kang, R.J., Mnich, M., M\u00fcller, T.: Induced matchings in subcubic planar graphs. SIAM J. Discret. Math. 26, 1383\u20131411 (2012)","journal-title":"SIAM J. Discret. Math."},{"key":"813_CR21","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1016\/j.jcss.2010.09.001","volume":"77","author":"I Kanj","year":"2011","unstructured":"Kanj, I., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. J. Comput. Syst. Sci. 77, 1058\u20131070 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"813_CR22","first-page":"327","volume":"16","author":"CW Ko","year":"2003","unstructured":"Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid cover. SIAM J. Discret. Math. 16, 327\u2013346 (2003)","journal-title":"SIAM J. Discret. Math."},{"key":"813_CR23","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 matching in subclasses of claw-free and $$P_5$$ P 5 -free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327\u2013346 (2003)","journal-title":"Algorithmica"},{"key":"813_CR24","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/j.dam.2011.08.027","volume":"160","author":"CM Krishnamurthy","year":"2012","unstructured":"Krishnamurthy, C.M., Sritharan, R.: Maximum induced matching problem on hhd-free graphs. Discret. Appl. Math. 160, 224\u2013230 (2012)","journal-title":"Discret. Appl. Math."},{"key":"813_CR25","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/S0020-0190(01)00185-5","volume":"81","author":"VV Lozin","year":"2002","unstructured":"Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inf. Process. Lett. 81, 7\u201311 (2002)","journal-title":"Inf. Process. Lett."},{"key":"813_CR26","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.tcs.2012.06.014","volume":"460","author":"VV Lozin","year":"2012","unstructured":"Lozin, V.V., Mosca, R.: Maximum regular induced subgraphs in $$2P_3$$ 2 P 3 -free graphs. Theor. Comput. Sci. 460, 26\u201333 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"813_CR27","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 in planar graphs. Discret. Appl. Math. 157, 715\u2013727 (2009)","journal-title":"Discret. Appl. Math."},{"key":"813_CR28","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. Discret. Algorithms 7, 181\u2013190 (2009)","journal-title":"J. Discret. Algorithms"},{"key":"813_CR29","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","volume":"5","author":"Y Orlovich","year":"2008","unstructured":"Orlovich, Y., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5, 584\u2013593 (2008)","journal-title":"Discret. Optim."},{"key":"813_CR30","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"JM Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"813_CR31","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-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15, 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"key":"813_CR32","doi-asserted-by":"crossref","unstructured":"Vassilaras, S., Christou, I.T.: On the optimal MAC layer capacity of delay tolerant mobile Ad Hoc networks with a finite number of nodes, In: 22nd annual IEEE international symposium on personal, indoor and mobile radio communication (PIMRC\u201911) (2011)","DOI":"10.1109\/PIMRC.2011.6140071"},{"key":"813_CR33","first-page":"58","volume":"7","author":"M Zito","year":"2000","unstructured":"Zito, M.: Linear time maximum induced matching algorithm for trees. Nord. J. Comput. 7, 58\u201363 (2000)","journal-title":"Nord. J. Comput."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-014-0813-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-014-0813-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-014-0813-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T12:58:14Z","timestamp":1565960294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-014-0813-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,22]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["813"],"URL":"https:\/\/doi.org\/10.1007\/s11590-014-0813-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,22]]}}}