{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:47Z","timestamp":1725663707322},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540557067"},{"type":"electronic","value":"9783540472759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55706-7_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:33:23Z","timestamp":1330252403000},"page":"292-303","source":"Crossref","is-referenced-by-count":0,"title":["Testing superperfection of k-trees"],"prefix":"10.1007","author":[{"given":"T.","family":"Kloks","sequence":"first","affiliation":[]},{"given":"H.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren and D. Seese, Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308\u2013340, 1991.","journal-title":"J. Algorithms"},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math., 23, 11\u201324, 1989.","journal-title":"Disc. Appl. Math."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender and T. Kloks, Better algorithms for the pathwidth and treewidth of graphs, Proceedings of the 18th International colloquium on Automata, Languages and Programming, 544\u2013555, Springer Verlag, Lecture Notes in Computer Science, vol. 510, 1991.","DOI":"10.1007\/3-540-54233-7_162"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"C. Berge and C. Chvatal, Topics on perfect graphs, Annals of Discrete Mathematics 21 1984.","DOI":"10.1016\/S0304-0208(08)72921-9"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences 13, 335\u2013379, 1976.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/pspum\/034\/525322","volume":"34","author":"J.E. Cohen","year":"1979","unstructured":"J.E. Cohen, J. Koml\u00f3s and T. Mueller, The probability of an interval graph, and why it matters, Proc. of Symposia in Pure Math. 34, 97\u2013115, 1979.","journal-title":"Proc. of Symposia in Pure Math."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/S0021-9800(70)80036-9","volume":"8","author":"P.C. Fishburn","year":"1970","unstructured":"P.C. Fishburn, An interval graph is not a comparability graph, J. Combin. Theory 8, 442\u2013443, 1970.","journal-title":"J. Combin. Theory"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15, 835\u2013855, 1965.","journal-title":"Pacific J. Math."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"T. Gallai, Transitiv orientierbaren Graphen, Acta Math. Sci. Hung. 18, 25\u201366, 1967.","journal-title":"Acta Math. Sci. Hung."},{"key":"25_CR10","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P.C. Gilmore","year":"1964","unstructured":"P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16, 539\u2013548, 1964.","journal-title":"Canad. J. Math."},{"key":"25_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"J. Lagergren and S. Arnborg, Finding minimal forbidden minors using a finite congruence, Proceedings of the 18th International colloquium on Automata, Languages and Programming, 532\u2013543, Springer Verlag, Lecture Notes in Computer Science, vol. 510, 1991.","DOI":"10.1007\/3-540-54233-7_161"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L. Lov\u00e1sz","year":"1972","unstructured":"L. Lov\u00e1sz, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253\u2013267, 1972.","journal-title":"Discrete Math."},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(91)90020-Y","volume":"12","author":"J. Matou\u0161ek","year":"1991","unstructured":"J. Matou\u0161ek and R. Thomas, Algorithms finding tree-decompositions of graphs, Journal of Algorithms 12, 1\u201322, 1991.","journal-title":"Journal of Algorithms"},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0021-9800(69)80056-6","volume":"7","author":"M. Jean","year":"1969","unstructured":"M. Jean, An interval graph is a comparability graph, J. Combin. Theory 7, 189\u2013190, 1969.","journal-title":"J. Combin. Theory"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnuelli","year":"1971","unstructured":"A. Pnuelli, A. Lempel, and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math. 23, 160\u2013175, 1971.","journal-title":"Canad. J. Math."},{"key":"25_CR17","unstructured":"B.A. Reed, Finding approximate separators and computing treewidth quickly, To appear in STOC'92."},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"N. Robertson and P.D. Seymour, Graph minors \u2014 a survey. In I. Anderson, editor, Surveys in Combinatorics 153\u2013171. Cambridge Univ. Press 1985.","DOI":"10.1017\/CBO9781107325678.009"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"J. Spinrad, On comparability and permutation graphs, SIAM J. Comp. 14, No. 3, August 1985.","DOI":"10.1137\/0214048"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '92"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55706-7_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:01:25Z","timestamp":1605646885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55706-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557067","9783540472759"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-55706-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}