{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:43Z","timestamp":1767340183233,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2019,1,19]],"date-time":"2019-01-19T00:00:00Z","timestamp":1547856000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"DOI":"10.1007\/s00453-018-00538-5","type":"journal-article","created":{"date-parts":[[2019,1,19]],"date-time":"2019-01-19T02:23:34Z","timestamp":1547864614000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Induced Matching Algorithms via Vertex Ordering Characterizations"],"prefix":"10.1007","author":[{"given":"Michel","family":"Habib","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2274-6773","authenticated-orcid":false,"given":"Lalla","family":"Mouatadid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,19]]},"reference":[{"issue":"6","key":"538_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1109\/JSAC.2004.830909","volume":"22","author":"H Balakrishnan","year":"2004","unstructured":"Balakrishnan, H., Barrett, C.L., Anil Kumar, V.S., Marathe, M.V.: Shripad Thite. The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks. IEEE J. Sel. Areas Commun. 22(6), 1069\u20131079 (2004)","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"3","key":"538_CR2","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/1978782.1978788","volume":"7","author":"V Bonifaci","year":"2011","unstructured":"Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: Minimizing flow time in the wireless gathering problem. ACM Trans. Algorithms 7(3), 33:1\u201333:20 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"538_CR3","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-007-9045-2","volume":"52","author":"A Brandst\u00e4dt","year":"2008","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: Maximum induced matchings for chordal graphs in linear time. Algorithmica 52(4), 440\u2013447 (2008)","journal-title":"Algorithmica"},{"key":"538_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"issue":"1\u20133","key":"538_CR5","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. Discrete Appl. Math. 24(1\u20133), 97\u2013102 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"538_CR6","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 Math. 278(1\u20133), 1\u20139 (2004)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"538_CR7","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 Math. 266(1\u20133), 133\u2013142 (2003)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"538_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"J-M Chang","year":"2003","unstructured":"Chang, J.-M.: Induced matchings in asteroidal triple-free graphs. Discrete Appl. Math. 132(1\u20133), 67\u201378 (2003)","journal-title":"Discrete Appl. Math."},{"key":"538_CR9","unstructured":"Charbit, P., Habib, M., Mouatadid, L., Naserasr, R.: Towards A unified view of linear structure on graph classes (2017). \n                  arXiv:1702.02133v1"},{"issue":"3","key":"538_CR10","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/11083856X","volume":"42","author":"DG Corneil","year":"2013","unstructured":"Corneil, D.G., Dalton, B., Habib, M.: Ldfs-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput. 42(3), 792\u2013807 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"538_CR11","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1137\/15M1012396","volume":"30","author":"DG Corneil","year":"2016","unstructured":"Corneil, D.G., Dusart, J., Habib, M., K\u00f6hler, E.: On the power of graph searching for cocomparability graphs. SIAM J. Discrete Math. 30(1), 569\u2013591 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"538_CR12","volume-title":"Forbidden Ordered Subgraphs. Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel","author":"P Damaschke","year":"1990","unstructured":"Damaschke, P.: Forbidden Ordered Subgraphs. Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel. Physica-Verlag HD, Germany (1990)"},{"issue":"1","key":"538_CR13","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 3(1), 79\u201391 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"538_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.3230140102","volume":"14","author":"S Even","year":"1984","unstructured":"Even, S., Goldreich, O., Moran, S., Tong, P.: On the np-completeness of certain network testing problems. Networks 14(1), 1\u201324 (1984)","journal-title":"Networks"},{"key":"538_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs Annals of Discrete Mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam (2004)"},{"issue":"1\u20133","key":"538_CR16","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.C.: Irredundancy in circular arc graphs. Discrete Appl. Math. 44(1\u20133), 79\u201389 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"538_CR17","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. Discrete Appl. Math. 101(1\u20133), 157\u2013165 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"538_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"MC Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Math. 43(1), 37\u201346 (1983)","journal-title":"Discrete Math."},{"key":"538_CR19","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.4230\/LIPIcs.ISAAC.2017.43","volume-title":"28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"M Habib","year":"2017","unstructured":"Habib, M., Mouatadid, L.: Maximum induced matching algorithms via vertex ordering characterizations. In: Okamoto, Y., Tokuyama, T. (eds.) 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 43:1\u201343:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). \n                  https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.43"},{"key":"538_CR20","unstructured":"Hell, P., Mohar, B., Rafiey, A.: Ordering without forbidden patterns. In: Algorithms\u2014ESA 2014\u201422th Annual European Symposium, Wroclaw, Poland, September 8\u201310, 2014. Proceedings, pp. 554\u2013565 (2014)"},{"key":"538_CR21","doi-asserted-by":"publisher","unstructured":"Joo, C., Sharma, G., Shroff, N.B., Mazumdar, R.R.: On the complexity of scheduling in wireless networks. EURASIP J. Wireless Commun. Netw. 2010, 418934 (2010). \n                  https:\/\/doi.org\/10.1155\/2010\/418934","DOI":"10.1155\/2010\/418934"},{"issue":"4","key":"538_CR22","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 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":"538_CR23","unstructured":"K\u00f6hler, E., Mouatadid, L.: Linear time lexdfs on cocomparability graphs. In: Algorithm Theory\u2014SWAT 2014\u201414th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2\u20134, 2014. Proceedings, pp. 319\u2013330 (2014)"},{"issue":"6","key":"538_CR24","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/j.ipl.2015.12.001","volume":"116","author":"E K\u00f6hler","year":"2016","unstructured":"K\u00f6hler, E., Mouatadid, L.: A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs. Inf. Process. Lett. 116(6), 391\u2013395 (2016)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"538_CR25","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D Kratsch","year":"1993","unstructured":"Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Discrete Math. 6(3), 400\u2013417 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"538_CR26","unstructured":"Kumar, R., Mahadevan, U., Sivakumar, D.: A graph-theoretic approach to extract storylines from search results. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washington, USA, August 22\u201325, 2004, pp. 216\u2013225 (2004)"},{"issue":"1","key":"538_CR27","doi-asserted-by":"publisher","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(1), 7\u201311 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"538_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"issue":"3","key":"538_CR29","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1137\/100793529","volume":"26","author":"GB Mertzios","year":"2012","unstructured":"Mertzios, G.B., Corneil, D.G.: A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM J. Discrete Math. 26(3), 940\u2013963 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"538_CR30","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: Linear-time algorithm for maximum-cardinality matching on cocomparability graphs (2017). \n                  arXiv:1703.05598"},{"key":"538_CR31","unstructured":"Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem in planar graphs. In: Frontiers in Algorithmics, First Annual International Workshop, FAW 2007, Lanzhou, China, August 1\u20133, 2007, Proceedings, pp. 325\u2013336 (2007)"},{"issue":"2","key":"538_CR32","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"538_CR33","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00538-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00538-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00538-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T09:29:54Z","timestamp":1580722194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00538-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,19]]},"references-count":33,"alternative-id":["538"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00538-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,1,19]]},"assertion":[{"value":"29 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}