{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T21:20:36Z","timestamp":1770240036306,"version":"3.49.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030895426","type":"print"},{"value":"9783030895433","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-89543-3_48","type":"book-chapter","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T02:03:25Z","timestamp":1634781805000},"page":"579-590","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Disconnected Matchings"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5164-1460","authenticated-orcid":false,"given":"Guilherme C. M.","family":"Gomes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9999-0029","authenticated-orcid":false,"given":"Bruno P.","family":"Masquio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7393-3464","authenticated-orcid":false,"given":"Paulo E. D.","family":"Pinto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4608-4559","authenticated-orcid":false,"given":"Vinicius F.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7538-7305","authenticated-orcid":false,"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,20]]},"reference":[{"key":"48_CR1","unstructured":"Abrishami, T., Chudnovsky, M., Dibek, C., Thomass\u00e9, S., Trotignon, N., Vu\u0161kovi\u0107, K.: Graphs with polynomially many minimal separators. arXiv preprint arXiv:2005.05042 (2020)"},{"key":"48_CR2","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. Discret. Appl. Math. 239, 38\u201344 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.01.002","journal-title":"Discret. Appl. Math."},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Heidelberg (2008). https:\/\/www.springer.com\/gp\/book\/9781846289699","DOI":"10.1007\/978-1-84628-970-5"},{"key":"48_CR4","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, PA, USA (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"1","key":"48_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. Discret. Appl. Math. 24(1), 97\u2013102 (1989). https:\/\/doi.org\/10.1016\/0166-218X(92)90275-F","journal-title":"Discret. Appl. Math."},{"key":"48_CR6","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":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/3-540-44679-6_34","volume-title":"Computing and Combinatorics","author":"LS Chandran","year":"2001","unstructured":"Chandran, L.S.: A linear time algorithm for enumerating all the minimum and minimal separators of a chordal graph. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 308\u2013317. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44679-6_34"},{"key":"48_CR8","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, vol. 3. Springer, Heidelberg (2015)"},{"issue":"1","key":"48_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0166-218X(99)00179-1","volume":"98","author":"JS Deogun","year":"1999","unstructured":"Deogun, J.S., Kloks, T., Kratsch, D., M\u00fcller, H.: On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discret. Appl. Math. 98(1), 39\u201363 (1999). https:\/\/doi.org\/10.1016\/S0166-218X(99)00179-1","journal-title":"Discret. Appl. Math."},{"key":"48_CR10","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":"48_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","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)"},{"key":"48_CR12","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964). https:\/\/doi.org\/10.4153\/CJM-1964-055-5","journal-title":"Can. J. Math."},{"issue":"1","key":"48_CR13","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. Discret. Math. 293(1), 129\u2013138 (2005). https:\/\/doi.org\/10.1016\/j.disc.2004.08.027","journal-title":"Discret. Math."},{"issue":"2","key":"48_CR14","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"},{"issue":"4","key":"48_CR15","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":"1","key":"48_CR16","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":"48_CR17","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":"48_CR18","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 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":"48_CR19","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. Discret. Appl. Math. 157(4), 715\u2013727 (2009). https:\/\/doi.org\/10.1016\/j.dam.2008.07.011","journal-title":"Discret. Appl. Math."},{"key":"48_CR20","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"},{"key":"48_CR21","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"},{"key":"48_CR22","doi-asserted-by":"publisher","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. STOC 1978, pp. 216\u2013226. Association for Computing Machinery, New York (1978). https:\/\/doi.org\/10.1145\/800133.804350","DOI":"10.1145\/800133.804350"},{"issue":"1\u20132","key":"48_CR23","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0304-3975(97)83809-1","volume":"180","author":"H Shen","year":"1997","unstructured":"Shen, H., Liang, W.: Efficient enumeration of all minimal separators in a graph. Theoret. Comput. Sci. 180(1\u20132), 169\u2013180 (1997)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-89543-3_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T02:18:58Z","timestamp":1634782738000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-89543-3_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030895426","9783030895433"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-89543-3_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 October 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tainan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2021\/","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":"131","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":"56","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":"43% - 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":"3.1","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":"2.2","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)"}}]}}