{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:02:50Z","timestamp":1725552170125},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_9","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"91-102","source":"Crossref","is-referenced-by-count":8,"title":["Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Meister","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S.. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"4","key":"9_CR2","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and Pathwidth of Permutation Graphs. SIAM Journal on Discrete Mathematics\u00a08(4), 606\u2013616 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3","key":"9_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D., M\u00fcller, H.: Treewidth and minimum fill-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications\u00a02(3), 1\u201323 (1998)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics\u00a06, 181\u2013188 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR5","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 Journal on Computing\u00a031, 212\u2013232 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics\u00a015, 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"key":"9_CR7","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, New York (1980)"},{"key":"9_CR8","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. Theoretical Computer Science\u00a0175, 309\u2013335 (1997)","journal-title":"Theoretical Computer Science"},{"key":"9_CR9","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 finite graphs by a set of intervals on the real line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(95)00095-9","volume":"64","author":"R.H. M\u00f6hring","year":"1996","unstructured":"M\u00f6hring, R.H.: Triangulating graphs without asteroidal triples. Discrete Applied Mathematics\u00a064, 281\u2013287 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/3-540-60084-1_68","volume-title":"Automata, Languages and Programming","author":"A. Parra","year":"1995","unstructured":"Parra, A., Scheffler, P.: How to Use the Minimal Separators of a Graph for its Chordal Triangulation. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 123\u2013134. Springer, Heidelberg (1995)"},{"key":"9_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. Discrete Applied Mathematics\u00a079, 171\u2013188 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D.J. Rose","year":"1970","unstructured":"Rose, D.J.: Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications\u00a032, 597\u2013609 (1970)","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM Jounal on Computing\u00a05, 266\u2013283 (1976)","journal-title":"SIAM Jounal on Computing"},{"key":"9_CR15","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 Journal on Algebraic and Discrete Methods\u00a02, 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic and 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\/11604686_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:33Z","timestamp":1619507073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11604686_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}