{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:30Z","timestamp":1759637850424,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_37","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"403-414","source":"Crossref","is-referenced-by-count":11,"title":["Minimal Interval Completions"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Suchan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-24587-2_7","volume-title":"Algorithms and Computation","author":"A. Berry","year":"2003","unstructured":"Berry, A., Heggernes, P., Villanger, Y.: A vertex incremental approach for dynamically maintaining chordal graphs. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 47\u201357. Springer, Heidelberg (2003)"},{"issue":"1","key":"37_CR2","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. on Computing\u00a031(1), 212\u2013232 (2001)","journal-title":"SIAM J. on Computing"},{"key":"37_CR3","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Co., New York (1978)"},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P.C. Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Canadian J. Math.\u00a016, 539\u2013548 (1964)","journal-title":"Canadian J. Math."},{"key":"37_CR5","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980)"},{"issue":"1","key":"37_CR6","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Bio.\u00a02(1), 139\u2013152 (1995)","journal-title":"J. Comput. Bio."},{"issue":"3","key":"37_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"2003","unstructured":"Gustedt, J.: On the pathwidth of chordal graphs. Discrete Applied Mathematics\u00a045(3), 233\u2013248 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"37_CR8","unstructured":"Heggernes, P.: Minimal triangulations of graphs: A survey. To appear Discrete Math."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal interval completions. Technical Report RR2005-04, LIFO - University of Orl\u00e9ans (2005), http:\/\/www.univ-orleans.fr\/SCIENCES\/LIFO\/prodsci\/rapports\/RR2005.htm.en","DOI":"10.1007\/11561071_37"},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theor. Comput. Sci.\u00a0175, 309\u2013335 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR11","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math.\u00a051, 45\u201364 (1962)","journal-title":"Fund. Math."},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Disc. Appl. Math.\u00a079, 171\u2013188 (1997)","journal-title":"Disc. Appl. Math."},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J.\u00a0Comput.\u00a05, 146\u2013160 (1976)","journal-title":"SIAM J.\u00a0Comput."},{"key":"37_CR14","doi-asserted-by":"publisher","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. Alg. Disc. Meth.\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T20:09:08Z","timestamp":1736021348000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11561071_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}