{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:38:29Z","timestamp":1725471509741},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540483816"},{"type":"electronic","value":"9783540483823"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11917496_20","type":"book-chapter","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T02:16:13Z","timestamp":1161137773000},"page":"217-228","source":"Crossref","is-referenced-by-count":4,"title":["Minimal Proper Interval Completions"],"prefix":"10.1007","author":[{"given":"Ivan","family":"Rapaport","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"}]}],"member":"297","reference":[{"issue":"1-3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(98)00005-5","volume":"84","author":"A. Berry","year":"1998","unstructured":"Berry, A., Bordat, J.P.: Separability Generalizes Dirac\u2019s Theorem. Discrete Applied Mathematics\u00a084(1-3), 43\u201353 (1998)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"20_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"20_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"key":"20_CR4","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":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1142\/S0129054199000125","volume":"10","author":"M. Habib","year":"1999","unstructured":"Habib, M., Paul, C., Viennot, L.: Partition Refinement Techniques: An Interesting Algorithmic Tool Kit. International Journal of Foundations of Computer Science\u00a010(2), 147\u2013170 (1999)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1-2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science\u00a0234(1-2), 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/11682462_55","volume-title":"LATIN 2006: Theoretical Informatics","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P., Mancini, F.: Minimal Split Completions of Graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 592\u2013604. Springer, Heidelberg (2006)"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/11561071_37","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Heggernes","year":"2005","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal Interval Completions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 403\u2013414. Springer, Heidelberg (2005)"},{"key":"20_CR9","first-page":"907","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA 2005","author":"P. Heggernes","year":"2005","unstructured":"Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time O(n\n                        \n                  \u03b1\n                \n                        log\n                        n) = o(n\n                        2.376). In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA 2005, pp. 907\u2013916. SIAM, Philadelphia (2005)"},{"issue":"3","key":"20_CR10","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/S0097539793258143","volume":"25","author":"H. Kaplan","year":"1996","unstructured":"Kaplan, H., Shamir, R.: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques. SIAM Journal on Computing\u00a025(3), 540\u2013561 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"20_CR11","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs. SIAM Journal on Computing\u00a028(5), 1906\u20131922 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR12","unstructured":"Kratsch, D., Spinrad, J.: Minimal fill in cO(n\n                        2.69) time. Discrete Applied Mathematics (to appear)"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B. Monien","year":"1986","unstructured":"Monien, B.: The bandwidth minimization problem for caterpillars with hair length 3 in NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a07, 505\u2013512 (1986)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"B.S. Panda","year":"2003","unstructured":"Panda, B.S., Das, S.K.: A linear time recognition algorithm for proper interval graphs. Information Processing Letters\u00a087(3), 153\u2013161 (2003)","journal-title":"Information Processing Letters"},{"key":"20_CR15","unstructured":"Rappaport, I., Suchan, K., Todinca, I.: Minimal proper interval completions. Technical Report RR-2006-02, LIFO - University of Orl\u00e9ans (2006), \n                  \n                    http:\/\/www.univ-orleans.fr\/SCIENCES\/LIFO\/prodsci\/rapports\/RR2006.htm.en"},{"key":"20_CR16","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."}],"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\/11917496_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:42:30Z","timestamp":1619494950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11917496_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540483816","9783540483823"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11917496_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}