{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T10:07:00Z","timestamp":1726135620423},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030865924"},{"type":"electronic","value":"9783030865931"}],"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-86593-1_12","type":"book-chapter","created":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:26:28Z","timestamp":1631391988000},"page":"176-189","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear-Time Minimal Cograph Editing"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Crespelle","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,9]]},"reference":[{"issue":"2","key":"12_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: Subexponential parameterized algorithm for interval completion. In: SODA 2016, pp. 1116\u20131131. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch78"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-642-39053-1_5","volume-title":"The Nature of Computation. Logic, Algorithms, Applications","author":"S B\u00f6cker","year":"2013","unstructured":"B\u00f6cker, S., Baumbach, J.: Cluster editing. In: Bonizzoni, P., Brattka, V., L\u00f6we, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 33\u201344. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39053-1_5"},{"issue":"2","key":"12_CR4","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/s00453-009-9339-7","volume":"60","author":"S B\u00f6cker","year":"2011","unstructured":"B\u00f6cker, S., Briesemeister, S., Klau, G.W.: Exact algorithms for cluster editing: evaluation and experiments. Algorithmica 60(2), 316\u2013334 (2011)","journal-title":"Algorithmica"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-662-48350-3_22","volume-title":"Algorithms - ESA 2015","author":"Ulrik Brandes","year":"2015","unstructured":"Brandes, Ulrik, Hamann, Michael, Strasser, Ben, Wagner, Dorothea: Fast quasi-threshold editing. In: Bansal, Nikhil, Finocchi, Irene (eds.) ESA 2015. LNCS, vol. 9294, pp. 251\u2013262. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_22"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-015-0043-7","volume":"10","author":"S Bruckner","year":"2015","unstructured":"Bruckner, S., H\u00fcffner, F., Komusiewicz, C.: A graph modification approach for finding core-periphery structures in protein interaction networks. Algorithms Mol. Biol. 10(1), 1\u201313 (2015)","journal-title":"Algorithms Mol. Biol."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ic.2017.01.008","volume":"253","author":"Y Cao","year":"2017","unstructured":"Cao, Y.: Unit interval editing is fixed-parameter tractable. Inf. Comput. 253, 109\u2013126 (2017)","journal-title":"Inf. Comput."},{"issue":"3","key":"12_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Burlingham, L.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"12_CR9","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D Corneil","year":"1985","unstructured":"Corneil, D., Perl, Y., Stewart, L.: A linear time recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"12_CR10","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","volume":"154","author":"C Crespelle","year":"2006","unstructured":"Crespelle, C., Paul, C.: Fully dynamic recognition algorithm and certificate for directed cographs. Discret. Appl. Math. 154(12), 1722\u20131741 (2006)","journal-title":"Discret. Appl. Math."},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Crespelle, C., Lokshtanov, D., Phan, T.H.D., Thierry, E.: Faster and enhanced inclusion-minimal cograph completion. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10627, pp. 210\u2013224. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71150-8_19","DOI":"10.1007\/978-3-319-71150-8_19"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2018.06.036","volume":"254","author":"C Crespelle","year":"2019","unstructured":"Crespelle, C., Perez, A., Todinca, I.: An $$o(n^2)$$-time algorithm for the minimal permutation completion problem. Discret. Appl. Math. 254, 80\u201395 (2019)","journal-title":"Discret. Appl. Math."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2012.12.031","volume":"494","author":"C Crespelle","year":"2013","unstructured":"Crespelle, C., Todinca, I.: An O(n$${}^{\\text{2 }}$$)-time algorithm for the minimal interval completion problem. Theor. Comput. Sci. 494, 75\u201385 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P Goldberg","year":"1995","unstructured":"Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1007\/s00453-012-9619-5","volume":"65","author":"S Guillemot","year":"2012","unstructured":"Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-)existence of polynomial kernels for $$P_l$$-free edge modification problems. Algorithmica 65(4), 900\u2013926 (2012)","journal-title":"Algorithmica"},{"issue":"5","key":"12_CR16","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/j.dam.2007.08.039","volume":"156","author":"P Heggernes","year":"2008","unstructured":"Heggernes, P., Mancini, F., Papadopoulos, C.: Minimal comparability completions of arbitrary graphs. Discret. Appl. Math. 156(5), 705\u2013718 (2008)","journal-title":"Discret. Appl. Math."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time $${O}(n^{\\alpha \\log n}) = o(n^{2.376})$$. SIAM J. Discrete Math. 19(4), 900\u2013913 (2005)","DOI":"10.1137\/S0895480104445010"},{"issue":"12","key":"12_CR18","doi-asserted-by":"publisher","first-page":"2659","DOI":"10.1016\/j.dam.2008.08.010","volume":"157","author":"P Heggernes","year":"2009","unstructured":"Heggernes, P., Mancini, F.: Minimal split completions. Discret. Appl. Math. 157(12), 2659\u20132669 (2009)","journal-title":"Discret. Appl. Math."},{"key":"12_CR19","unstructured":"Hellmuth, M., Fritz, A., Wieseke, N., Stadler, P.F.: Techniques for the cograph editing problem: Module merge is equivalent to editing P4s. CoRR abs\/1509.06983 (2015)"},{"issue":"7","key":"12_CR20","doi-asserted-by":"publisher","first-page":"2058","DOI":"10.1073\/pnas.1412770112","volume":"112","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth, M., Wieseke, N., Lechner, M., Lenhof, H.P., Middendorf, M., Stadler, P.F.: Phylogenomics with paralogs. PNAS 112(7), 2058\u20132063 (2015)","journal-title":"PNAS"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Jia, S., et al.: Defining and identifying cograph communities in complex networks. New J. Phys. 17(1), 013044 (2015)","DOI":"10.1088\/1367-2630\/17\/1\/013044"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.: Mapping the genome: some combinatorial problems arising in molecular biology. In: 25th ACM Symposium on Theory of Computing (STOC 1993), pp. 278\u2013285. ACM (1993)","DOI":"10.1145\/167088.167170"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), pp. 93\u2013106. ACM (2008)","DOI":"10.1145\/1376616.1376629"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2011.11.040","volume":"461","author":"Y Liu","year":"2012","unstructured":"Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. Theoret. Comput. Sci. 461, 45\u201354 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"12_CR25","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1016\/j.dam.2009.01.016","volume":"158","author":"D Lokshtanov","year":"2010","unstructured":"Lokshtanov, D., Mancini, F., Papadopoulos, C.: Characterizing and computing minimal cograph completions. Discrete Appl. Math. 158(7), 755\u2013764 (2010)","journal-title":"Discrete Appl. Math."},{"key":"12_CR26","unstructured":"Mancini, F.: Graph Modification Problems Related to Graph Classes. Ph.D. Thesis, University of Bergen, Norway (2008)"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Nastos, J., Gao, Y.: Bounded search tree algorithms for parametrized cograph deletion: Efficient branching rules by exploiting structures of special graph classes. Discrete Math., Alg. and Appl. 4 (2012)","DOI":"10.1142\/S1793830912500085"},{"issue":"3","key":"12_CR28","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.socnet.2013.05.001","volume":"35","author":"J Nastos","year":"2013","unstructured":"Nastos, J., Gao, Y.: Familial groups in social networks. Social Networks 35(3), 439\u2013450 (2013)","journal-title":"Social Networks"},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0022-0000(81)90022-2","volume":"22","author":"T Ohtsuki","year":"1981","unstructured":"Ohtsuki, T., Mori, H., Kashiwabara, T., Fujisawa, T.: On minimal augmentation of a graph to obtain an interval graph. J. Comput. Syst. Sci. 22(1), 60\u201397 (1981)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"12_CR30","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.ipl.2007.11.013","volume":"106","author":"I Rapaport","year":"2008","unstructured":"Rapaport, I., Suchan, K., Todinca, I.: Minimal proper interval completions. Inf. Process. Lett. 106(5), 195\u2013202 (2008)","journal-title":"Inf. Process. Lett."},{"key":"12_CR31","unstructured":"Schoch, D., Brandes, U.: Stars, neighborhood inclusion and network centrality. In: SIAM Workshop on Network Science (2015)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86593-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:29:52Z","timestamp":1631392192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86593-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030865924","9783030865931"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86593-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"9 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","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":"12 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/fct2021\/","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":"94","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":"30","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":"32% - 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":"8.54","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)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic. There are papers of 2 invited talks also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}