{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:14Z","timestamp":1781078174260,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["948057, 683080"],"award-info":[{"award-number":["948057, 683080"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533349","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Treelike Decompositions for Transductions of Sparse Graphs"],"prefix":"10.1145","author":[{"given":"Jan","family":"Dreier","sequence":"first","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandra","family":"Kiefer","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.118"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"e_1_3_2_1_3_1","volume-title":"Sebastian Siebertz, and St\u00e9phan Thomass\u00e9.","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet , Jaroslav Ne\u0161et\u0159il , Patrice Ossona de Mendez , Sebastian Siebertz, and St\u00e9phan Thomass\u00e9. 2021 . Twin-width and permutations. CoRR abs\/2102.06880(2021). arXiv:2102.06880https:\/\/arxiv.org\/abs\/2102.06880 \u00c9douard Bonnet, Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, Sebastian Siebertz, and St\u00e9phan Thomass\u00e9. 2021. Twin-width and permutations. CoRR abs\/2102.06880(2021). arXiv:2102.06880https:\/\/arxiv.org\/abs\/2102.06880"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1342756"},{"key":"e_1_3_2_1_5_1","volume-title":"Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Dreier Jan","year":"2021","unstructured":"Jan Dreier . 2021 . Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021 . IEEE, 1\u201313. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470680 10.1109\/LICS52264.2021.9470680 Jan Dreier. 2021. Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021. IEEE, 1\u201313. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470680"},{"key":"e_1_3_2_1_6_1","unstructured":"Jan Dreier Jakub Gajarsk\u00fd Sandra Kiefer Micha\u0142 Pilipczuk and Szymon Toru\u0144czyk. 2022. Treelike Decompositions for Transductions of Sparse Graphs. CoRR abs\/2201.11082(2022). arXiv:2201.11082https:\/\/arxiv.org\/abs\/2201.11082  Jan Dreier Jakub Gajarsk\u00fd Sandra Kiefer Micha\u0142 Pilipczuk and Szymon Toru\u0144czyk. 2022. Treelike Decompositions for Transductions of Sparse Graphs. CoRR abs\/2201.11082(2022). arXiv:2201.11082https:\/\/arxiv.org\/abs\/2201.11082"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935314"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_1_10_1","unstructured":"Jakub Gajarsk\u00fd Micha\u0142 Pilipczuk and Szymon Toru\u0144czyk. 2021. Stable graphs of bounded twin-width. CoRR abs\/2107.03711(2021). arXiv:2107.03711https:\/\/arxiv.org\/abs\/2107.03711  Jakub Gajarsk\u00fd Micha\u0142 Pilipczuk and Szymon Toru\u0144czyk. 2021. Stable graphs of bounded twin-width. CoRR abs\/2107.03711(2021). arXiv:2107.03711https:\/\/arxiv.org\/abs\/2107.03711"},{"key":"e_1_3_2_1_11_1","volume-title":"Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15, 1","author":"Ganian Robert","year":"2019","unstructured":"Robert Ganian , Petr Hlin\u011bn\u00fd , Jaroslav Ne\u0161et\u0159il , Jan Obdr\u017e\u00e1lek , and Patrice Ossona de Mendez . 2019 . Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15, 1 (2019). https:\/\/doi.org\/10.23638\/LMCS-15(1:7)2019 10.23638\/LMCS-15(1:7)2019 Robert Ganian, Petr Hlin\u011bn\u00fd, Jaroslav Ne\u0161et\u0159il, Jan Obdr\u017e\u00e1lek, and Patrice Ossona de Mendez. 2019. Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15, 1 (2019). https:\/\/doi.org\/10.23638\/LMCS-15(1:7)2019"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2271704"},{"key":"e_1_3_2_1_14_1","volume-title":"Vol.\u00a028","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez . 2012. Sparsity \u2014 Graphs , Structures, and Algorithms. Algorithms and Combinatorics , Vol.\u00a028 . Springer . https:\/\/doi.org\/10.1007\/978-3-642-27875-4 10.1007\/978-3-642-27875-4 Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity \u2014 Graphs, Structures, and Algorithms. Algorithms and Combinatorics, Vol.\u00a028. Springer. https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.120"},{"key":"e_1_3_2_1_16_1","first-page":"P4","article-title":"Clustering Powers of Sparse Graphs","volume":"27","author":"Ne\u0161et\u0159il Jaroslav","year":"2020","unstructured":"Jaroslav Ne\u0161et\u0159il , Patrice Ossona de Mendez , Micha\u0142 Pilipczuk , and Xuding Zhu . 2020 . Clustering Powers of Sparse Graphs . Electron. J. Comb. 27 , 4 (2020), P4 .17. https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v27i4p17 Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, Micha\u0142 Pilipczuk, and Xuding Zhu. 2020. Clustering Powers of Sparse Graphs. Electron. J. Comb. 27, 4 (2020), P4.17. https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v27i4p17","journal-title":"Electron. J. Comb."},{"key":"e_1_3_2_1_17_1","volume-title":"\u201cSparsity","author":"Pilipczuk Marcin","unstructured":"Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Sebastian Siebertz . Winter semesters 2017\/18 and 2019\/20. Lecture notes for the course \u201cSparsity \u201d given at Faculty of Mathematics, Informatics , and Mechanics of the University of Warsaw . Available https:\/\/www.mimuw.edu.pl\/~mp248287\/sparsity2. Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Sebastian Siebertz. Winter semesters 2017\/18 and 2019\/20. Lecture notes for the course \u201cSparsity\u201d given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw. Available https:\/\/www.mimuw.edu.pl\/~mp248287\/sparsity2."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209178"},{"key":"e_1_3_2_1_19_1","first-page":"145","article-title":"On the Density of Families of Sets. J. Comb. Theory","volume":"13","author":"Sauer Norbert","year":"1972","unstructured":"Norbert Sauer . 1972 . On the Density of Families of Sets. J. Comb. Theory , Ser. A 13 , 1 (1972), 145 \u2013 147 . https:\/\/doi.org\/10.1016\/0097-3165(72)90019-2 10.1016\/0097-3165(72)90019-2 Norbert Sauer. 1972. On the Density of Families of Sets. J. Comb. Theory, Ser. A 13, 1 (1972), 145\u2013147. https:\/\/doi.org\/10.1016\/0097-3165(72)90019-2","journal-title":"Ser. A"},{"key":"e_1_3_2_1_20_1","first-page":"247","article-title":"A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J","volume":"41","author":"Shelah Saharon","year":"1972","unstructured":"Saharon Shelah . 1972 . A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J . Math. 41 (1972), 247 \u2013 261 . Saharon Shelah. 1972. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J. Math. 41(1972), 247\u2013261.","journal-title":"Math."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103214"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Haifa Israel","acronym":"LICS '22","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"]},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:09Z","timestamp":1750186929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":22,"alternative-id":["10.1145\/3531130.3533349","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533349","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}