{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:05Z","timestamp":1759639025841,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319711492"},{"type":"electronic","value":"9783319711508"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-71150-8_19","type":"book-chapter","created":{"date-parts":[[2017,11,16]],"date-time":"2017-11-16T00:48:21Z","timestamp":1510793301000},"page":"210-224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Faster and Enhanced Inclusion-Minimal Cograph Completion"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Crespelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thi Ha Duong","family":"Phan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Thierry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,17]]},"reference":[{"issue":"2","key":"19_CR1","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica 6(2), 83\u201396 (1986)","journal-title":"Combinatorica"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-39890-5_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Berry","year":"2003","unstructured":"Berry, A., Heggernes, P., Simonet, G.: The minimum degree heuristic and the minimal triangulation process. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 58\u201370. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39890-5_6"},{"key":"19_CR3","first-page":"49","volume":"11","author":"H Bodlaender","year":"1995","unstructured":"Bodlaender, H., Downey, R., Fellows, M., Hallett, M., Wareham, H.: Parameterized complexity analysis in computational biology. Comput. Appl. Biosci. 11, 49\u201357 (1995)","journal-title":"Comput. Appl. Biosci."},{"key":"19_CR4","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 \u2013 ESA 2015","author":"U Brandes","year":"2015","unstructured":"Brandes, U., Hamann, M., Strasser, B., Wagner, D.: Fast Quasi-threshold editing. In: Bansal, N., Finocchi, I. (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":"19_CR5","first-page":"55","volume":"5","author":"C Capelle","year":"2002","unstructured":"Capelle, C., Habib, M., de Montgolfier, F.: Graph decompositions and factorizing permutations. Discrete Math. Theoret. Comput. Sci. 5(1), 55\u201370 (2002)","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"issue":"3","key":"19_CR6","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.S.: Complement reducible graphs. Discrete Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"19_CR7","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":"19_CR8","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. Discrete Appl. Math. 154(12), 1722\u20131741 (2006)","journal-title":"Discrete Appl. Math."},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-662-53174-7_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"C Crespelle","year":"2016","unstructured":"Crespelle, C., Perez, A., Todinca, I.: An $$\\cal{O}(n^2)$$ time algorithm for the minimal permutation completion problem. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 103\u2013115. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53174-7_8"},{"key":"19_CR10","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^2)$$-time algorithm for the minimal interval completion problem. Theor. Comput. Sci. 494, 75\u201385 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: 19th ACM Symposium on Theory of Computing (STOC 1987), pp. 365\u2013372. ACM (1987)","DOI":"10.1145\/28395.28434"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-662-48350-3_35","volume-title":"Algorithms \u2013 ESA 2015","author":"PG Drange","year":"2015","unstructured":"Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 411\u2013423. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_35"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Gabow, H., Bentley, J., Tarjan, R.: Scaling and related techniques for geometry problems. In: 16th ACM Symposium on Theory of Computing (STOC 1984), pp. 135\u2013143. ACM (1984)","DOI":"10.1145\/800057.808675"},{"key":"19_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":"19_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":"19_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. Discrete Appl. Math. 156(5), 705\u2013718 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1137\/S0895480104445010","volume":"19","author":"P Heggernes","year":"2005","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)","journal-title":"SIAM J. Discrete Math."},{"issue":"12","key":"19_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. Discrete Appl. Math. 157(12), 2659\u20132669 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"19_CR19","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"},{"issue":"4","key":"19_CR20","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Society 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Society"},{"issue":"1","key":"19_CR21","doi-asserted-by":"publisher","first-page":"013044","DOI":"10.1088\/1367-2630\/17\/1\/013044","volume":"17","author":"S Jia","year":"2015","unstructured":"Jia, S., Gao, L., Gao, Y., Nastos, J., Wang, Y., Zhang, X., Wang, H.: Defining and identifying cograph communities in complex networks. New J. Phys. 17(1), 013044 (2015)","journal-title":"New J. Phys."},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"D Kendall","year":"1969","unstructured":"Kendall, D.: Incidence matrices, interval graphs, and seriation in archeology. Pacific J. Math. 28, 565\u2013570 (1969)","journal-title":"Pacific J. Math."},{"key":"19_CR23","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":"19_CR24","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":"19_CR25","unstructured":"Mancini, F.: Graph modification problems related to graph classes. Ph.D. thesis, University of Bergen, Norway (2008)"},{"issue":"1","key":"19_CR26","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":"3","key":"19_CR27","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.jctb.2006.06.006","volume":"97","author":"S Oum","year":"2007","unstructured":"Oum, S., Seymour, P.D.: Testing branch-width. J. Comb. Theory Ser. B 97(3), 385\u2013393 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"19_CR28","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."},{"issue":"3","key":"19_CR29","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71150-8_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T13:46:23Z","timestamp":1709819183000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-71150-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319711492","9783319711508"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71150-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"17 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","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":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/anl.sjtu.edu.cn\/cocoa2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}