<div class="csl-bib-body">
<div class="csl-entry">Dreier, J., Gajarský, J., Kiefer, S., Pilipczuk, M., & Toruńczyk, S. (2022). Treelike Decompositions for Transductions of Sparse Graphs. In <i>Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Thirty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Haifa, Israel. Association for Computing Machinery, Inc. https://doi.org/10.1145/3531130.3533349</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/142207
-
dc.description.abstract
We give new decomposition theorems for classes of graphs that can be transduced in frst-order logic from classes of sparse graphs - more precisely, from classes of bounded expansion and nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size O(ne), where n is the vertex count and e > 0 is any fxed real. This solves an open problem posed by Gajarský et al. (ACM TOCL '20) and also by Brianski et al. (SIDMA '21).
en
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
bounded expansion
en
dc.subject
nowhere dense
en
dc.subject
shrubdepth
en
dc.subject
transduction
en
dc.title
Treelike Decompositions for Transductions of Sparse Graphs
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.contributor.affiliation
University of Warsaw, Poland
-
dc.contributor.affiliation
Max Planck Institute for Software Systems, Germany
-
dc.contributor.affiliation
University of Warsaw, Poland
-
dc.contributor.affiliation
University of Warsaw, Poland
-
dc.relation.isbn
978-1-4503-9351-5
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
-
tuw.relation.publisher
Association for Computing Machinery, Inc.
-
tuw.book.chapter
31
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1145/3531130.3533349
-
dc.identifier.libraryid
AC17202135
-
dc.description.numberOfPages
14
-
tuw.author.orcid
0000-0002-2662-5303
-
tuw.author.orcid
0000-0003-4614-9444
-
tuw.author.orcid
0000-0002-1130-9033
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
Thirty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
en
dc.description.sponsorshipexternal
European Union’s Horizon 2020
-
dc.description.sponsorshipexternal
European Union’s Horizon 2020
-
dc.relation.grantnoexternal
683080
-
dc.relation.grantnoexternal
948057
-
tuw.event.startdate
02-08-2022
-
tuw.event.enddate
05-08-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Haifa
-
tuw.event.country
IL
-
tuw.event.presenter
Gajarský, Jakub
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
dc.relation.isnewversionof
https://doi.org/10.48550/arXiv.2201.11082
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.fulltext
with Fulltext
-
item.grantfulltext
open
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
