{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:23Z","timestamp":1725511763598},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_21","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"236-247","source":"Crossref","is-referenced-by-count":9,"title":["Characterizing 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":[{"issue":"1-2","key":"21_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci.\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.disc.2005.12.017","volume":"306","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. Discrete Mathematics\u00a0306(3), 337\u2013350 (2006)","journal-title":"Discrete Mathematics"},{"key":"21_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K., Leuker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR4","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. Comput.\u00a031, 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"21_CR5","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J. Diaz","year":"2002","unstructured":"Diaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv.\u00a034(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"21_CR6","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1287\/moor.1030.0079","volume":"29","author":"S.P. Fekete","year":"2004","unstructured":"Fekete, S.P., Schepers, J.: A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res.\u00a029(2), 353\u2013368 (2004)","journal-title":"Math. Oper. Res."},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: D\u00edaz, J., et al. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 568\u2013580. Springer, Heidelberg (2004)"},{"key":"21_CR8","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"21_CR9","series-title":"Prentice-Hall series in computational mathematics","volume-title":"Computer Solution of Large Sparse Positive Definite","author":"A. George","year":"1981","unstructured":"George, A., Liu, J.W.: Computer Solution of Large Sparse Positive Definite. Prentice-Hall series in computational mathematics. Prentice-Hall, Englewood Cliffs (1981)"},{"issue":"1","key":"21_CR10","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., et al.: Four strikes against physical mapping of dna. Journal of Computational Biology\u00a02(1), 139\u2013152 (1995)","journal-title":"Journal of Computational Biology"},{"key":"21_CR11","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, San Diego (1980)"},{"issue":"3","key":"21_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"Gustedt, J.: On the pathwidth of chordal graphs. Discrete Appl. Math.\u00a045(3), 233\u2013248 (1993)","journal-title":"Discrete Appl. Math."},{"key":"21_CR13","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., et al.: Minimal interval completions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 403\u2013414. Springer, Heidelberg (2005)"},{"unstructured":"Heggernes, P., et al.: Characterizing minimal interval completions. Towards better understanding of profile and pathwidth. Technical Report LIFO Research Report RR 2006-09, LIFO - University of Orleans, France (2006)","key":"21_CR14"},{"issue":"5","key":"21_CR15","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 J. Comput.\u00a028(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"21_CR16","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1137\/S0097539798336073","volume":"30","author":"A. Natanzon","year":"2000","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput.\u00a030(4), 1067\u20131079 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/S089547989936443X","volume":"23","author":"B.W. Peyton","year":"2001","unstructured":"Peyton, B.W.: Minimal orderings revisited. SIAM J. Matrix Anal. Appl.\u00a023(1), 271\u2013294 (2001)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"21_CR18","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. Comput.\u00a05, 146\u2013160 (1976)","journal-title":"SIAM J. Comput."},{"key":"21_CR19","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","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:11:48Z","timestamp":1605762708000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_21","relation":{},"subject":[]}}