{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:07:10Z","timestamp":1787497630882,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540651956","type":"print"},{"value":"9783540494942","type":"electronic"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[[1998]]},"DOI":"10.1007\/10692760_8","type":"book-chapter","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T12:35:37Z","timestamp":1277901337000},"page":"88-99","source":"Crossref","is-referenced-by-count":5,"title":["A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking"],"prefix":"10.1007","author":[{"given":"Hajo","family":"Broersma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability\u2014A survey. BIT\u00a025, 2\u201323 (1985)","journal-title":"BIT"},{"key":"8_CR2","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 J. Alg. Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/3-540-56402-0_39","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Bodlaender","year":"1993","unstructured":"Bodlaender, H.: Kayles on special classes of graphs - An application of Sprague-Grundy theory. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol.\u00a0657, pp. 90\u2013102. Springer, Heidelberg (1993)"},{"key":"8_CR4","first-page":"1","volume":"11","author":"H. Bodlaender","year":"1993","unstructured":"Bodlaender, H.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. Bodlaender","year":"1996","unstructured":"Bodlaender, H.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/S0895480195282550","volume":"11","author":"H. Bodlaender","year":"1998","unstructured":"Bodlaender, H., Deogun, J.S., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Rankings of graphs. SIAM Journal on Discrete Mathematics\u00a011, 168\u2013181 (1998)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating tree-width, pathwidth and minimum elimination tree height. Journal of Algorithms\u00a018, 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM Journal on Discrete Mathematics\u00a08, 606\u2013616 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR9","volume-title":"Introduction to algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms. MlT Press, Cambridge (1990)"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D.G. Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics\u00a010, 399\u2013430 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/3-540-60084-1_82","volume-title":"Automata, Languages and Programming","author":"D.G. Corneil","year":"1995","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: A linear time algorithm to compute dominating pairs in asteroidal triple-free graphs. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 292\u2013302. Springer, Heidelberg (1995)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1007\/3-540-57785-8_187","volume-title":"11th Annual Symposium on Theoretical Aspects of Computer Science","author":"J.S. Deogun","year":"1994","unstructured":"Deogun, J.S., Kloks, T., Kratsch, D., M\u00fcller, H.: On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 747\u2013758. Springer, Heidelberg (1994)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"8_CR14","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":"8_CR15","doi-asserted-by":"crossref","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order\u00a011, 47\u201360 (1994)","DOI":"10.1007\/BF01462229"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth - Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth - Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S009753979427087X","volume":"27","author":"T. Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D.: Finding all minimal separators of a graph. SIAM Journal on Computing\u00a027, 605\u2013613 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BFb0024501","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Asteroidal sets in graphs. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 229\u2013241. Springer, Heidelberg (1997)"},{"key":"8_CR19","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 aster-oidal triple-free graphs. Theoretical Computer Science\u00a0175, 309\u2013335 (1997)","journal-title":"Theoretical Computer Science"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/BFb0009493","volume-title":"Algorithms and Computation","author":"T. Kloks","year":"1996","unstructured":"Kloks, T., M\u00fcller, H., Wong, C.K.: Vertex ranking of asteroidal triple-free graphs. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 174\u2013182. Springer, Heidelberg (1996)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: Area efficient graph layouts for VLSI. In: Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 270\u2013281 (1980)","DOI":"10.1109\/SFCS.1980.13"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","DOI":"10.4064\/fm-51-1-45-64"},{"key":"8_CR23","unstructured":"Lin, I.J., McKee, T.A., West, D.B.: Leafage of chordal graphs, Manuscript (1994)"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Liu, J.W.H.: The role of elimination trees in sparse factorization. SIAM Journal of Matrix Analysis and Applications\u00a011, 134\u2013172 (1990)","DOI":"10.1137\/0611010"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R.H.: Triangulating graphs without asteroidal triples. Discrete Applied Mathematics\u00a064, 281\u2013287 (1996)","DOI":"10.1016\/0166-218X(95)00095-9"},{"key":"8_CR26","unstructured":"Parra, A.: Structural and algorithmic aspects of chordal graph embeddings, PhD. thesis, Technische Universit\u00e4t Berlin (1996)"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02941616","volume":"62","author":"E. Prisner","year":"1992","unstructured":"Prisner, E.: Representing triangulated graphs in stars. Abh. Math. Sem. Univ. Hamburg\u00a062, 29\u201341 (1992)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"8_CR28","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 Journal on Computing\u00a05, 266\u2013283 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/jgt.3190020311","volume":"2","author":"J.R. Walter","year":"1978","unstructured":"Walter, J.R.: Representations of chordal graphs as subtrees of a tree. Journal of Graph Theory\u00a02, 265\u2013267 (1978)","journal-title":"Journal of Graph Theory"},{"key":"8_CR30","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\/10692760_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T12:08:33Z","timestamp":1559218113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10692760_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651956","9783540494942"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/10692760_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}