{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:13:42Z","timestamp":1775837622871,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132575","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"391-400","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Linear time low tree-width partitions and algorithmic consequences"],"prefix":"10.1145","author":[{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"first","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrice Ossona","family":"de Mendez","sequence":"additional","affiliation":[{"name":"\u00c9cole des Hautes \u00c9tudes en Sciences Sociales, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_3_1","first-page":"142","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","year":"1990","unstructured":"B. Courcelle . Graph rewriting: an algebraic and logic approach . In J. van Leeuwen, editor, Handbook of Theoretical Computer Science , volume 2 , chapter 5, pages 142 -- 193 . Elsevier , Amsterdam , 1990 . B. Courcelle. Graph rewriting: an algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, chapter 5, pages 142--193. Elsevier, Amsterdam, 1990."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings if the 11th Annual Symposium on Theoretical Aspects of Computer Science","volume":"775","author":"Deogun J.","year":"1994","unstructured":"J. Deogun , T. Kloks , D. Kratsch , and H. Muller . On vertex ranking for permutation and other graphs. In Springer, editor , Proceedings if the 11th Annual Symposium on Theoretical Aspects of Computer Science , volume 775 of Lecture Notes in Computer Science, pages 747--758 , 1994 . J. Deogun, T. Kloks, D. Kratsch, and H. Muller. On vertex ranking for permutation and other graphs. In Springer, editor, Proceedings if the 11th Annual Symposium on Theoretical Aspects of Computer Science, volume 775 of Lecture Notes in Computer Science, pages 747--758, 1994."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.001"},{"key":"e_1_3_2_1_7_1","first-page":"632","volume-title":"Proc. 6th Symp. Discrete Algorithms","author":"Eppstein D.","year":"1995","unstructured":"D. Eppstein . Subgraph isomorphism in planar graphs and related problems . In Proc. 6th Symp. Discrete Algorithms , pages 632 -- 640 . ACM and SIAM, January 1995 . D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proc. 6th Symp. Discrete Algorithms, pages 632--640. ACM and SIAM, January 1995."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594262613"},{"key":"e_1_3_2_1_12_1","volume-title":"European Journal of Combinatorics","author":"Ne\u0161et\u0159il J.","year":"2005","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion I. decompositions . European Journal of Combinatorics , 2005 . (submitted). J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion I. decompositions. European Journal of Combinatorics, 2005. (submitted)."},{"key":"e_1_3_2_1_13_1","volume-title":"European Journal of Combinatorics","author":"Ne\u0161et\u0159il J.","year":"2005","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects . European Journal of Combinatorics , 2005 . (submitted). J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. European Journal of Combinatorics, 2005. (submitted)."},{"key":"e_1_3_2_1_14_1","volume-title":"European Journal of Combinatorics","author":"Ne\u0161et\u0159il J.","year":"2005","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion III. restricted dualities . European Journal of Combinatorics , 2005 . (submitted). J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion III. restricted dualities. European Journal of Combinatorics, 2005. (submitted)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"J.\n      Ne\u0161et\u0159il\n     and \n      P.\n      Ossona de Mendez\n    .\n  The grad of a graph and classes with bounded expansion\n  . In A. Raspaud and O. Delmas editors 7th International Colloquium on Graph Theory volume \n  22\n   of \n  Electronic Notes in Discrete Mathematics pages \n  101\n  --\n  106\n  . \n  Elsevier 2005\n  .  J. Ne\u0161et\u0159il and P. Ossona de Mendez. The grad of a graph and classes with bounded expansion. In A. Raspaud and O. Delmas editors 7th International Colloquium on Graph Theory volume 22 of Electronic Notes in Discrete Mathematics pages 101--106. Elsevier 2005.","DOI":"10.1016\/j.endm.2005.06.018"},{"key":"e_1_3_2_1_16_1","volume-title":"European Journal of Combinatorics","author":"Ne\u0161et\u0159il J.","year":"2005","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds . European Journal of Combinatorics , 2005 . (in press). J. Ne\u0161et\u0159il and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 2005. (in press)."},{"key":"e_1_3_2_1_17_1","first-page":"415","article-title":"Complexity of the subgraph problem","volume":"2","author":"Ne\u0161et\u0159il J.","year":"1985","unstructured":"J. Ne\u0161et\u0159il and S. Poljak . Complexity of the subgraph problem . Comment. Math. Univ. Carol., 26 . 2 : 415 -- 420 , 1985 . J. Ne\u0161et\u0159il and S. Poljak. Complexity of the subgraph problem. Comment. Math. Univ. Carol., 26.2:415--420, 1985.","journal-title":"Comment. Math. Univ. Carol., 26"},{"key":"e_1_3_2_1_20_1","first-page":"18","volume-title":"Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science, number 484 in Lecture Notes in Computer Science","author":"Plehn J.","year":"1991","unstructured":"J. Plehn and B. Voigt . Finding minimally weighted subgraphs. In Springer-Verlag, editor , Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science, number 484 in Lecture Notes in Computer Science , pages 18 -- 29 , 1991 . J. Plehn and B. Voigt. Finding minimally weighted subgraphs. In Springer-Verlag, editor, Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science, number 484 in Lecture Notes in Computer Science, pages 18--29, 1991."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90161-0"},{"key":"e_1_3_2_1_24_1","volume-title":"Colloquium at Emory University","author":"Szemer\u00e9di E.","year":"1994","unstructured":"E. Szemer\u00e9di . Colloquium at Emory University , Atlanta, GA , April 22. 1994 . E. Szemer\u00e9di. Colloquium at Emory University, Atlanta, GA, April 22. 1994."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00008-9"},{"key":"e_1_3_2_1_26_1","volume-title":"Bled, Slovenia.","author":"Thomas R.","year":"1995","unstructured":"R. Thomas . Problem session of the Third Slovene Conference on Graph Theory , Bled, Slovenia. 1995 . R. Thomas. Problem session of the Third Slovene Conference on Graph Theory, Bled, Slovenia. 1995."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594196"}],"event":{"name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA","acronym":"STOC06","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132575","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:51Z","timestamp":1750263531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":25,"alternative-id":["10.1145\/1132516.1132575","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132575","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}