{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T02:23:21Z","timestamp":1774319001938,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008769","name":"Julius-Maximilians-Universit\u00e4t W\u00fcrzburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>A bipartite graph $$G=(U,V,E)$$<\/jats:tex-math>\n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n U<\/mml:mi>\n ,<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is convex<\/jats:italic> if the vertices in V<\/jats:italic> can be linearly ordered such that for each vertex $$u\\in U$$<\/jats:tex-math>\n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n U<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the neighbors of u<\/jats:italic> are consecutive in the ordering of V<\/jats:italic>. An induced matching<\/jats:italic>H<\/jats:italic> of\u00a0G<\/jats:italic> is a matching for which no edge of E<\/jats:italic> connects endpoints of two different edges of H<\/jats:italic>. We show that in a convex bipartite graph with n<\/jats:italic> vertices and m<\/jats:italic>weighted<\/jats:italic> edges, an induced matching of maximum total weight can be computed in $$O(n+m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. An unweighted<\/jats:italic> convex bipartite graph has a representation of size O<\/jats:italic>(n<\/jats:italic>) that records for each vertex $$u\\in U$$<\/jats:tex-math>\n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n U<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the first and last neighbor in the ordering of V<\/jats:italic>. Given such a compact representation<\/jats:italic>, we compute an induced matching of maximum cardinality in O<\/jats:italic>(n<\/jats:italic>) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers<\/jats:italic>. A chain cover is a covering of the edge set by chain subgraphs<\/jats:italic>, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O<\/jats:italic>(n<\/jats:italic>) time. If no compact representation is given, the cover can be computed in $$O(n+m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted<\/jats:italic> problem versions had a running time of $$O(n^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Brandst\u00e4dt et al. in Theor. Comput. Sci. 381(1\u20133):260\u2013265, 2007. 10.1016\/j.tcs.2007.04.006<\/jats:ext-link>). The weighted<\/jats:italic> case has not been considered before.<\/jats:p>","DOI":"10.1007\/s00453-021-00904-w","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T14:02:48Z","timestamp":1641477768000},"page":"1064-1080","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4532-3765","authenticated-orcid":false,"given":"Boris","family":"Klemz","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0351-5945","authenticated-orcid":false,"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"issue":"1","key":"904_CR1","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.tcs.2007.05.012","volume":"381","author":"K Asdre","year":"2007","unstructured":"Asdre, K., Nikolopoulos, S.D.: NP-completeness results for some problems on subclasses of bipartite and chordal graphs. Theor. Comput. Sci. 381(1), 248\u2013259 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.05.012","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"904_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"904_CR3","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.04.006","volume":"381","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Eschen, E.M., Sritharan, R.: The induced matching and chain subgraph cover problems for convex bipartite graphs. Theor. Comput. Sci. 381(1\u20133), 260\u2013265 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.04.006","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"904_CR4","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). https:\/\/doi.org\/10.1007\/s00453-007-9045-2","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"904_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). https:\/\/doi.org\/10.1016\/0166-218X(92)90275-F","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"904_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 Math. 266(1\u20133), 133\u2013142 (2003). https:\/\/doi.org\/10.1016\/S0012-365X(02)00803-8","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"904_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"JM Chang","year":"2003","unstructured":"Chang, J.M.: Induced matchings in asteroidal triple-free graphs. Discrete Appl. Math. 132(1\u20133), 67\u201378 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(03)00390-1","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"904_CR8","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1002\/jgt.3190150508","volume":"15","author":"G Ding","year":"1991","unstructured":"Ding, G.: Covering the edges with consecutive sets. J. Graph Theory 15(5), 559\u2013562 (1991). https:\/\/doi.org\/10.1002\/jgt.3190150508","journal-title":"J. Graph Theory"},{"issue":"1","key":"904_CR9","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). https:\/\/doi.org\/10.1016\/j.jda.2004.05.001","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"904_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0167-6377(84)90068-3","volume":"3","author":"G Gallo","year":"1984","unstructured":"Gallo, G.: An $$O(n \\log n)$$ algorithm for the convex bipartite matching problem. Oper. Res. Lett. 3(1), 31\u201334 (1984). https:\/\/doi.org\/10.1016\/0167-6377(84)90068-3","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"904_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14(3), 313\u2013316 (1967). https:\/\/doi.org\/10.1002\/nav.3800140304","journal-title":"Nav. Res. Logist. Q."},{"issue":"1\u20133","key":"904_CR12","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). https:\/\/doi.org\/10.1016\/S0166-218X(99)00194-8","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"904_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discrete Appl. Math. 28(1), 35\u201344 (1990). https:\/\/doi.org\/10.1016\/0166-218X(90)90092-Q","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"904_CR14","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s00224-011-9378-8","volume":"50","author":"R Hung","year":"2012","unstructured":"Hung, R.: Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput. Syst. 50(4), 721\u2013738 (2012). https:\/\/doi.org\/10.1007\/s00224-011-9378-8","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"904_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1287\/ijoc.1070.0232","volume":"20","author":"I Katriel","year":"2008","unstructured":"Katriel, I.: Matchings in node-weighted convex bipartite graphs. INFORMS J. Comput. 20(2), 205\u2013211 (2008). https:\/\/doi.org\/10.1287\/ijoc.1070.0232","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"904_CR16","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_5$$-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37(4), 327\u2013346 (2003). https:\/\/doi.org\/10.1007\/s00453-003-1035-4","journal-title":"Algorithmica"},{"issue":"1","key":"904_CR17","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). https:\/\/doi.org\/10.1016\/S0020-0190(01)00185-5","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"904_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011). https:\/\/doi.org\/10.1016\/j.cosrev.2010.09.009","journal-title":"Comput. Sci. Rev."},{"issue":"1\u20133","key":"904_CR19","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1\u20133), 291\u2013298 (1996). https:\/\/doi.org\/10.1016\/0012-365X(95)00057-4","journal-title":"Discrete Math."},{"key":"904_CR20","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s10878-020-00611-2","volume":"40","author":"BS Panda","year":"2020","unstructured":"Panda, B.S., Pandey, A., Chaudhary, J., Dane, P., Kashyap, M.: Maximum weight induced matching in some subclasses of bipartite graphs. J. Combin. Optim. 40, 713\u2013732 (2020). https:\/\/doi.org\/10.1007\/s10878-020-00611-2","journal-title":"J. Combin. Optim."},{"key":"904_CR21","doi-asserted-by":"crossref","unstructured":"Pandey, A., Panda, B.S., Dane, P., Kashyap, M.: Induced matching in some subclasses of bipartite graphs. In: Gaur, D.R., Narayanaswamy, N.S. (eds.) Algorithms and Discrete Applied Mathematics\u2013Third International Conference, CALDAM 2017, Sancoale, Goa, India, February 16\u201318, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10156, pp. 308\u2013319. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-53007-9_27","DOI":"10.1007\/978-3-319-53007-9_27"},{"key":"904_CR22","unstructured":"Schrijver, A.: Combinatorial Optimization\u2014Polyhedra and Efficiency, Vol.\u00a0B, Algorithms and Combinatorics, vol.\u00a024. Springer (2003)"},{"issue":"1","key":"904_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s00453-007-9006-9","volume":"53","author":"J Soares","year":"2009","unstructured":"Soares, J., Stefanes, M.A.: Algorithms for maximum independent set in convex bipartite graphs. Algorithmica 53(1), 35\u201349 (2009). https:\/\/doi.org\/10.1007\/s00453-007-9006-9","journal-title":"Algorithmica"},{"key":"904_CR24","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"},{"issue":"12","key":"904_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G Steiner","year":"1996","unstructured":"Steiner, G., Yeomans, J.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 31(12), 91\u201396 (1996). https:\/\/doi.org\/10.1016\/0898-1221(96)00079-X","journal-title":"Comput. Math. Appl."},{"issue":"1","key":"904_CR26","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). https:\/\/doi.org\/10.1016\/0020-0190(82)90077-1","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"904_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(97)00036-4","volume":"205","author":"CW Yu","year":"1998","unstructured":"Yu, C.W., Chen, G.H., Ma, T.H.: On the complexity of the $$k$$-chain subgraph cover problem. Theor. Comput. Sci. 205(1\u20132), 85\u201398 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00036-4","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00904-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00904-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00904-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:08:44Z","timestamp":1647443324000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00904-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["904"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00904-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"14 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest whatsoever.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}