{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:09:42Z","timestamp":1743142182903,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206238"},{"type":"electronic","value":"9783031206245"}],"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_44","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"730-745","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity Results on\u00a0Untangling Red-Blue Matchings"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3645-4210","authenticated-orcid":false,"given":"Arun Kumar","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7565-8593","authenticated-orcid":false,"given":"Sandip","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-028X","authenticated-orcid":false,"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2664-0650","authenticated-orcid":false,"given":"Yan","family":"Gerard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5985-2169","authenticated-orcid":false,"given":"Bastien","family":"Rivier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"issue":"2","key":"44_CR1","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/s00454-015-9709-7","volume":"54","author":"O Aichholzer","year":"2015","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete Comput. Geom. 54(2), 368\u2013389 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Akiyama, J., Alon, N.: Disjoint simplices and geometric hypergraphs. In: Third International Conference on Combinatorial Mathematics, pp. 1\u20133 (1989)","DOI":"10.1111\/j.1749-6632.1989.tb22429.x"},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(85)90065-0","volume":"31","author":"MJ Atallah","year":"1985","unstructured":"Atallah, M.J.: A matching problem in the plane. J. Comput. Syst. Sci. 31(1), 63\u201370 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Bereg, S., Ito, H.: Transforming graphs with the same degree sequence. In: Computational Geometry and Graph Theory, pp. 25\u201332 (2008)","DOI":"10.1007\/978-3-540-89550-3_3"},{"key":"44_CR5","first-page":"627","volume":"25","author":"S Bereg","year":"2017","unstructured":"Bereg, S., Ito, H.: Transforming graphs with the same graphic sequence. J. Inf. Process. 25, 627\u2013633 (2017)","journal-title":"J. Inf. Process."},{"key":"44_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.comgeo.2019.01.008","volume":"81","author":"A Biniaz","year":"2019","unstructured":"Biniaz, A., Maheshwari, A., Smid, M.: Flip distance to some plane configurations. Comput. Geom. 81, 12\u201321 (2019)","journal-title":"Comput. Geom."},{"key":"44_CR7","unstructured":"Bonamy, M., et al.: The perfect matching reconfiguration problem. In: 44th International Symposium on Mathematical Foundations of Computer Science. LIPIcs, vol. 138, pp. 80:1\u201380:14 (2019)"},{"key":"44_CR8","unstructured":"Bonnet, \u00c9., Miltzow, T.: Flip distance to a Non-crossing perfect matching. Computing Research Repository abs\/1601.05989 (2016)"},{"issue":"1","key":"44_CR9","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60\u201380 (2009)","journal-title":"Comput. Geom."},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-030-38919-2_7","volume-title":"SOFSEM 2020: Theory and Practice of Computer Science: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20\u201324, 2020, Proceedings","author":"N Bousquet","year":"2020","unstructured":"Bousquet, N., Joffard, A.: Approximating shortest connected graph transformation for trees. In: Chatzigeorgiou, A., Dondi, R., Herodotou, H., Kapoutsis, C., Manolopoulos, Y., Papadopoulos, G.A., Sikora, F. (eds.) SOFSEM 2020: Theory and Practice of Computer Science: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20\u201324, 2020, Proceedings, pp. 76\u201387. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_7"},{"issue":"03","key":"44_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M De Berg","year":"2012","unstructured":"De Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(03), 187\u2013205 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"44_CR12","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s00453-013-9801-4","volume":"68","author":"M Englert","year":"2014","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68(1), 190\u2013264 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"44_CR13","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1017\/S0963548313000096","volume":"22","author":"PL Erd\u0151s","year":"2013","unstructured":"Erd\u0151s, P.L., Kir\u00e1ly, Z., Mikl\u00f3s, I.: On the swap-distances of different realizations of a graphical degree sequence. Comb. Prob. and Comput. 22(3), 366\u2013383 (2013)","journal-title":"Comb. Prob. and Comput."},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph i. J. Soc. Ind. Appl. Math. 10(3), 496\u2013506 (1962)","DOI":"10.1137\/0110037"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph ii. uniqueness. J. Soc. Ind. Appl. Math. 11(1), 135\u2013147 (1963)","DOI":"10.1137\/0111010"},{"issue":"2","key":"44_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J Hershberger","year":"1992","unstructured":"Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT Numer. Math. 32(2), 249\u2013267 (1992)","journal-title":"BIT Numer. Math."},{"key":"44_CR17","first-page":"127","volume":"409","author":"J van den Heuvel","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surv. Comb. 409, 127\u2013160 (2013)","journal-title":"Surv. Comb."},{"issue":"3","key":"44_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/PL00009464","volume":"22","author":"F Hurtado","year":"1999","unstructured":"Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22(3), 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"12","key":"44_CR19","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., et al.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"44_CR20","unstructured":"Joffard, A.: Graph domination and reconfiguration problems. Ph.D. thesis, Universit\u00e9 Claude Bernard Lyon 1 (2020)"},{"issue":"4","key":"44_CR21","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0012-365X(72)90093-3","volume":"3","author":"CL Lawson","year":"1972","unstructured":"Lawson, C.L.: Transforming triangulations. Discrete Math. 3(4), 365\u2013372 (1972)","journal-title":"Discrete Math."},{"key":"44_CR22","unstructured":"van Leeuwen, J.: Untangling a traveling salesman tour in the plane. In: 7th Workshop on Graph-Theoretic Concepts in Computer Science (1981)"},{"key":"44_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"A Lubiw","year":"2015","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17\u201323 (2015)","journal-title":"Comput. Geom."},{"key":"44_CR24","doi-asserted-by":"crossref","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4) (2018)","DOI":"10.3390\/a11040052"},{"key":"44_CR25","doi-asserted-by":"crossref","unstructured":"Oda, Y., Watanabe, M.: The number of flips required to obtain non-crossing convex cycles. In: Kyoto International Conference on Computational Geometry and Graph Theory, pp. 155\u2013165 (2007)","DOI":"10.1007\/978-3-540-89550-3_17"},{"issue":"5","key":"44_CR26","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.comgeo.2014.01.001","volume":"47","author":"A Pilz","year":"2014","unstructured":"Pilz, A.: Flip distance between triangulations of a planar point set is apx-hard. Comput. Geom. 47(5), 589\u2013604 (2014)","journal-title":"Comput. Geom."},{"issue":"3","key":"44_CR27","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/S0895480197331156","volume":"12","author":"TG Will","year":"1999","unstructured":"Will, T.G.: Switching distance between graphs with the same degrees. SIAM J. Discrete Math. 12(3), 298\u2013306 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"44_CR28","unstructured":"Wu, R., Chang, J., Lin, J.: On the maximum switching number to obtain non-crossing convex cycles. In: 26th Workshop on Combinatorial Mathematics and Computation Theory, pp. 266\u2013273 (2009)"}],"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_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T23:08:44Z","timestamp":1667084924000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_44","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":"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)"}}]}}