{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:54Z","timestamp":1759637814201},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_8","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"103-115","source":"Crossref","is-referenced-by-count":1,"title":["An $$\\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Crespelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Perez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1007\/11561071_69","volume-title":"Algorithms \u2013 ESA 2005","author":"A Bergeron","year":"2005","unstructured":"Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of K permutations, with applications to modular decomposition of graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 779\u2013790. Springer, Heidelberg (2005)"},{"issue":"13","key":"8_CR2","doi-asserted-by":"crossref","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Appl. Math. 154(13), 1824\u20131844 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/s00453-008-9273-0","volume":"58","author":"C Crespelle","year":"2010","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs. Algorithmica 58(2), 405\u2013432 (2010)","journal-title":"Algorithmica"},{"key":"8_CR4","doi-asserted-by":"crossref","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."},{"issue":"3","key":"8_CR5","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: a survey. Discrete Math. 306(3), 297\u2013317 (2006)","journal-title":"Discrete Math."},{"issue":"5","key":"8_CR6","doi-asserted-by":"crossref","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":"8_CR7","doi-asserted-by":"crossref","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":"8_CR8","doi-asserted-by":"crossref","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":"8_CR9","doi-asserted-by":"crossref","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":"8_CR10","unstructured":"Mancini, F.: Graph Modification Problems Related to Graph Classes. Ph.D. thesis, University of Bergen, Norway (2008)"},{"issue":"1","key":"8_CR11","doi-asserted-by":"crossref","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":"1","key":"8_CR12","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1137\/0205012","volume":"5","author":"T Ohtsuki","year":"1976","unstructured":"Ohtsuki, T.: A fast algorithm for finding an optimal ordering for vertex elimination on a graph. SIAM J. Comput. 5(1), 133\u2013145 (1976)","journal-title":"SIAM J. Comput."},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.ipl.2007.11.013","volume":"5","author":"I Rapaport","year":"2008","unstructured":"Rapaport, I., Suchan, K., Todinca, I.: Minimal proper interval completions. Inf. Process. Lett. 5, 195\u2013202 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"8_CR14","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM. J. Algebraic Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM. J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T15:57:44Z","timestamp":1498319864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}