{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:04Z","timestamp":1777539964427,"version":"3.51.4"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031206238","type":"print"},{"value":"9783031206245","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20624-5_4","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"54-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Weighted Connected Matchings"],"prefix":"10.1007","author":[{"given":"Guilherme C. M.","family":"Gomes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno P.","family":"Masquio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulo E. D.","family":"Pinto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinicius F. dos","family":"Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.dam.2018.01.002","volume":"239","author":"J Baste","year":"2018","unstructured":"Baste, J., Rautenbach, D.: Degenerate matchings and edge colorings. Discrete Appl. Math. 239, 38\u201344 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.01.002","journal-title":"Discrete Appl. Math."},{"key":"4_CR2","unstructured":"Biasi, M.D.: Max-weight connected subgraph problem in planar graphs. Theor. Comput. Sci. Stack Exch. https:\/\/cstheory.stackexchange.com\/q\/21669"},{"key":"4_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008, 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 9, pp. 165\u2013176 (2011). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.165","DOI":"10.4230\/LIPIcs.STACS.2011.165"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008). https:\/\/www.springer.com\/gp\/book\/9781846289699","DOI":"10.1007\/978-1-84628-970-5"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"4_CR7","unstructured":"de C. M. Gomes, G., Masquio, B.P., Pinto, P.E.D., dos Santos, V.F., Szwarcfiter, J.L.: Disconnected matchings. CoRR abs\/2112.09248 (2021). https:\/\/arxiv.org\/abs\/2112.09248"},{"issue":"1","key":"4_CR8","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), 97\u2013102 (1989). https:\/\/doi.org\/10.1016\/0166-218X(92)90275-F","journal-title":"Discrete Appl. Math."},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/3-540-36478-1_5","volume-title":"Combinatorial Optimization \u2014 Eureka, You Shrink!","author":"K Cameron","year":"2003","unstructured":"Cameron, K.: Connected matchings. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization \u2014 Eureka, You Shrink! LNCS, vol. 2570, pp. 34\u201338. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36478-1_5"},{"key":"4_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Duan, R., Pettie, S., Su, H.H.: Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms 14(1) (2018). https:\/\/doi.org\/10.1145\/3155301","DOI":"10.1145\/3155301"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl Bureau Stand. B 69, 125\u2013130 (1965). https:\/\/doi.org\/10.6028\/jres.069B.013","journal-title":"J. Res. Natl Bureau Stand. B"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965). https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"key":"4_CR14","doi-asserted-by":"publisher","unstructured":"F\u00fcrst, M., Rautenbach, D.: On some hard and some tractable cases of the maximum acyclic matching problem. Ann. Oper. Res. 279(1), 291\u2013300 (2019). https:\/\/doi.org\/10.1007\/s10479-019-03311-1","DOI":"10.1007\/s10479-019-03311-1"},{"issue":"4","key":"4_CR15","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977). https:\/\/doi.org\/10.1137\/0132071","journal-title":"SIAM J. Appl. Math."},{"key":"4_CR16","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.disc.2004.08.027","volume":"293","author":"W Goddard","year":"2005","unstructured":"Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.: Generalized subgraph-restricted matchings in graphs. Discrete Math. 293(1), 129\u2013138 (2005). https:\/\/doi.org\/10.1016\/j.disc.2004.08.027","journal-title":"Discrete Math."},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-001-0004-z","volume":"31","author":"MC Golumbic","year":"2001","unstructured":"Golumbic, M.C., Hirst, T., Lewenstein, M.: Uniquely restricted matchings. Algorithmica 31(2), 139\u2013154 (2001). https:\/\/doi.org\/10.1007\/s00453-001-0004-z","journal-title":"Algorithmica"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-030-89543-3_48","volume-title":"Computing and Combinatorics","author":"GCM Gomes","year":"2021","unstructured":"Gomes, G.C.M., Masquio, B.P., Pinto, P.E.D., dos Santos, V.F., Szwarcfiter, J.L.: Disconnected matchings. In: Chen, C.-Y., Hon, W.-K., Hung, L.-J., Lee, C.-W. (eds.) COCOON 2021. LNCS, vol. 13025, pp. 579\u2013590. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-89543-3_48"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1007\/s00453-021-00904-w","volume":"84","author":"B Klemz","year":"2022","unstructured":"Klemz, B., Rote, G.: Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs. Algorithmica 84(4), 1064\u20131080 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00904-w","journal-title":"Algorithmica"},{"issue":"4","key":"4_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). https:\/\/doi.org\/10.1007\/s00453-003-1035-4","journal-title":"Algorithmica"},{"issue":"2","key":"4_CR23","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982). https:\/\/doi.org\/10.1137\/0211025","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR24","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."},{"key":"4_CR25","unstructured":"Masquio, B.P.: Emparelhamentos desconexos. Master\u2019s thesis, Universidade do Estado do Rio de Janeiro (2019). http:\/\/www.bdtd.uerj.br\/handle\/1\/7663"},{"key":"4_CR26","doi-asserted-by":"publisher","unstructured":"Micali, S., Vazirani, V.V.: An $${O}(\\sqrt{|V|}|{E}|)$$ algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201327, October 1980. https:\/\/doi.org\/10.1109\/SFCS.1980.12","DOI":"10.1109\/SFCS.1980.12"},{"issue":"4","key":"4_CR27","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.dam.2008.07.011","journal-title":"Discrete Appl. Math."},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-030-48966-3_31","volume-title":"Combinatorial Algorithms","author":"BS Panda","year":"2020","unstructured":"Panda, B.S., Chaudhary, J.: Acyclic matching in some subclasses of graphs. In: G\u0105sieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 409\u2013421. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48966-3_31"},{"issue":"3","key":"4_CR29","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. Comb. Optim. 40(3), 713\u2013732 (2020). https:\/\/doi.org\/10.1007\/s10878-020-00611-2","journal-title":"J. Comb. Optim."},{"key":"4_CR30","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","DOI":"10.1016\/0196-6774(86)90023-4"}],"container-title":["Lecture Notes in Computer Science","LATIN 2022: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20624-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T23:04:25Z","timestamp":1667084665000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guanajuato","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/delta.cs.cinvestav.mx\/~francisco\/Latin22\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"114","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}