{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:31:58Z","timestamp":1743100318358,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031221040"},{"type":"electronic","value":"9783031221057"}],"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.springernature.com\/gp\/researchers\/text-and-data-mining"},{"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.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22105-7_10","type":"book-chapter","created":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T05:12:32Z","timestamp":1672549952000},"page":"106-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the\u00a0Complexity of\u00a0Minimum Maximal Acyclic Matchings"],"prefix":"10.1007","author":[{"given":"Juhi","family":"Chaudhary","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sounaka","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. S.","family":"Panda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"key":"10_CR1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"2012","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Spaccamela, A.M., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (2012)"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan, C., et al.: The many facets of upper domination. Theoret. Comput. Sci. 717, 2\u201325 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2014.06.001","volume":"196","author":"N Boria","year":"2015","unstructured":"Boria, N., Croce, F.D., Paschos, V.T.: On the max min vertex cover problem. Discret. Appl. Math. 196, 62\u201371 (2015)","journal-title":"Discret. Appl. Math."},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2021.05.036","volume":"882","author":"J Chaudhary","year":"2021","unstructured":"Chaudhary, J., Panda, B.S.: On the complexity of minimum maximal uniquely restricted matching. Theoret. Comput. Sci. 882, 15\u201328 (2021)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.disopt.2010.02.006","volume":"8","author":"P Damaschke","year":"2011","unstructured":"Damaschke, P.: Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover. Discret. Optim. 8(1), 18\u201324 (2011)","journal-title":"Discret. Optim."},{"key":"10_CR6","unstructured":"Dublois, L., Hanaka, T.,. Ghadikolaei, M.K, Lampis, M., Melissinos, N.: (In)approximability of maximum minimal FVS. In: Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC). LIPIcs, vo. 181, pp. 3:1\u20133:14 (2020)"},{"key":"10_CR7","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)","journal-title":"Can. J. Math."},{"key":"10_CR8","unstructured":"F\u00fcrst, M.: Restricted matchings. Ph.D. thesis, Universit\u00e4t Ulm (2019)"},{"key":"10_CR9","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, New York (1979)"},{"issue":"1\u20133","key":"10_CR10","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\u20133), 129\u2013138 (2005)","journal-title":"Discret. Math."},{"issue":"7","key":"10_CR11","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard, W., Henning, M.A.: Independent domination in graphs: a survey and recent results. Discret. Math. 313(7), 839\u2013854 (2013)","journal-title":"Discret. Math."},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"MC Golumbic","year":"1978","unstructured":"Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2(2), 155\u2013163 (1978)","journal-title":"J. Graph Theory"},{"key":"10_CR13","unstructured":"Kann, V.: On the approximability of NP-complete optimization problems. Ph.D. thesis, Royal Institute of Technology Stockholm (1992)"},{"issue":"4","key":"10_CR14","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1137\/0208049","volume":"8","author":"MS Krishnamoorthy","year":"1979","unstructured":"Krishnamoorthy, M.S., Deo, N.S.: Node-deletion NP-complete problems. SIAM J. Comput. 8(4), 619\u2013625 (1979)","journal-title":"SIAM J. Comput."},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.endm.2006.06.019","volume":"24","author":"VV Lepin","year":"2006","unstructured":"Lepin, V.V.: A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. Electron. Notes Discrete Math. 24, 111\u2013116 (2006)","journal-title":"Electron. Notes Discrete Math."},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Society (2009)","DOI":"10.1090\/chel\/367"},{"issue":"3","key":"10_CR17","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","volume":"5","author":"YL Orlovich","year":"2008","unstructured":"Orlovich, Y.L., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5(3), 584\u2013593 (2008)","journal-title":"Discret. Optim."},{"key":"10_CR18","unstructured":"Orlovich, Y.L., Zverovich, I.E.: Maximal induced matchings of minimum\/maximum size. Technical report, DIMACS TR 2004-26 (2004)"},{"key":"10_CR19","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":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-319-64419-6_29","volume-title":"Theoretical Computer Science and Discrete Mathematics","author":"BS Panda","year":"2017","unstructured":"Panda, B.S., Pandey, A.: On the complexity of minimum cardinality maximal uniquely restricted matching in graphs. In: Arumugam, S., Bagga, J., Beineke, L.W., Panda, B.S. (eds.) ICTCSDM 2016. LNCS, vol. 10398, pp. 218\u2013227. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-64419-6_29"},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85\u201389 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"10_CR23","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"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-031-22105-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T22:03:58Z","timestamp":1680213838000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22105-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031221040","9783031221057"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22105-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 January 2023","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":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","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":"22 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2022\/","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":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"101","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":"39","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":"12","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":"39% - 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","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":"5","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)"}}]}}