{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:26Z","timestamp":1725664046279},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562795"},{"type":"electronic","value":"9783540475019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56279-6_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:57:19Z","timestamp":1330253839000},"page":"116-125","source":"Crossref","is-referenced-by-count":6,"title":["Approximating treewidth and pathwidth of some classes of perfect graphs"],"prefix":"10.1007","author":[{"given":"Ton","family":"Kloks","sequence":"first","affiliation":[]},{"given":"Hans","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT 25, 2\u201323, 1985.","journal-title":"BIT"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth. 8, 277\u2013284, 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"13_CR3","doi-asserted-by":"publisher","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":"13_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, SIAM J. Alg. Disc. Meth. 7, 305\u2013314, 1986.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"13_CR5","doi-asserted-by":"publisher","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":"13_CR6","doi-asserted-by":"crossref","unstructured":"C. Berge and C. Chvatal, Topics on Perfect Graphs, Annals of Discrete Math. 21, 1984.","DOI":"10.1016\/S0304-0208(08)72921-9"},{"key":"13_CR7","volume-title":"Technical report RUU-CS-92-12","author":"H.L. Bodlaender","year":"1992","unstructured":"H.L. Bodlaender, A tourist guide through treewidth, Technical report RUU-CS-92-12, Department of computer science, Utrecht University, Utrecht, The Netherlands, 1992. To appear in: Proceedings 7th International Meeting of Young Computer Scientists, Springer Verlag, Lecture Notes in Computer Science."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, J. Gilbert, H. Hafsteinsson and T. Kloks, Approximating treewidth, pathwidth and minimum elimination tree height, In G. Schmidt and R. Berghammer, editors, Proceedings 17th International Workshop on Graph-Theoretic Concepts in Computer Science WG'91, 1\u201312, Springer Verlag, Lecture Notes in Computer Science, vol. 570, 1992.","DOI":"10.1007\/3-540-55121-2_1"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"H. Bodlaender and R.H. M\u00f6hring, The pathwidth and treewidth of cographs, In Proceedings 2nd Scandinavian Workshop on Algorithm Theory, 301\u2013309, Springer Verlag, Lecture Notes in Computer Science vol. 447, 1990.","DOI":"10.1007\/3-540-52846-6_99"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"H. 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":"13_CR11","first-page":"53","volume-title":"Lecture Notes in Comp. Science vol. 199","author":"A. Brandst\u00c4dt","year":"1985","unstructured":"A. Brandst\u00c4dt and D. Kratsch, On the restriction of some NP-complete graph problems to permutation graphs, Fundamentals of Computation Theory, proc. FCT 1985, 53\u201362, Lecture Notes in Comp. Science vol. 199, Springer Verlag, New York, 1985."},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","volume":"54","author":"A. Brandst\u00c4dt","year":"1987","unstructured":"A. Brandst\u00c4dt and D. Kratsch, On domination problems for permutation and other perfect graphs, Theor. Comput. Sci. 54, 181\u2013198, 1987.","journal-title":"Theor. Comput. Sci."},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation 85, 12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"B. Courcelle, The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues, Report 8852, University Bordeaux 1, 1988.","DOI":"10.1007\/BF02088013"},{"key":"13_CR15","first-page":"192","volume-title":"Handbook of Theoretical Computer Science, Vol. B","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, Graph rewriting: an algebraic and logical approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. B, 192\u2013242, Amsterdam, 1990. North Holland Publ. Comp."},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25, 71\u201376, 1961.","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"S. Even, A. Pnueli and A. Lempel, Permutation graphs and transitive graphs, J. Assoc. Comput. Mach. 19, 400\u2013410, 1972.","journal-title":"J. Assoc. Comput. Mach."},{"key":"13_CR18","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"Gilmore","year":"1964","unstructured":"Gilmore and Hoffman, A characterization of comparability and interval graphs, Canad. J. Math. 16, 539\u2013548, 1964.","journal-title":"Canad. J. Math."},{"key":"13_CR19","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":"13_CR20","unstructured":"J. Gustedt, Pathwidth for chordal graphs is NP-complete. Preprint TU Berlin, 1989."},{"key":"13_CR21","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":"13_CR22","first-page":"527","volume-title":"Handbook of Theoretical Computer Science, A: Algorithms an Complexity Theory","author":"J. Leeuwen van","year":"1990","unstructured":"J. van Leeuwen, Graph algorithms. In Handbook of Theoretical Computer Science, A: Algorithms an Complexity Theory, 527\u2013631, Amsterdam, 1990. North Holland Publ. Comp."},{"key":"13_CR23","doi-asserted-by":"publisher","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":"13_CR24","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, 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":"13_CR25","doi-asserted-by":"crossref","unstructured":"B. Reed, Finding approximate separators and computing treewidth quickly, To appear in: Proceedings STOC'92, 1992.","DOI":"10.1145\/129712.129734"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"N. Robertson and P.D. Seymour, Graph minors\u2014A survey. In I. Anderson, editor, Surveys in Combinatorics, 153\u2013171. Cambridge Univ. Press 1985.","DOI":"10.1017\/CBO9781107325678.009"},{"key":"13_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour, Graph minors II. Algorithmic aspects of treewidth. J. Algorithms 7, 309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"13_CR28","volume-title":"NFS-CBMS Monograph no. 29","author":"F.S. Roberts","year":"1978","unstructured":"F.S. Roberts, Graph theory and its applications to problems of society, NFS-CBMS Monograph no. 29 (SIAM Publications, Philadelphia, PA. 1978)."},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"M.C. Golumbic","year":"1983","unstructured":"M.C. Golumbic, D. Rotem and J. Urrutia, Comparability graphs and intersection graphs, Discrete Math. 43, 37\u201346, 1983.","journal-title":"Discrete Math."},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"J. Spinrad, On comparability and permutation graphs, SIAM J. Comp. 14, No. 3, August 1985.","DOI":"10.1137\/0214048"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"R. Sundaram, K. Sher Singh and C. Pandu Rangan, Treewidth of circular arc graphs, Manuscript 1991.","DOI":"10.1007\/BFb0028248"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56279-6_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T18:21:54Z","timestamp":1687285314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56279-6_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562795","9783540475019"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-56279-6_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}