Talks and Poster Presentations (with Proceedings-Entry):
J. Dreier:
"Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes";
Talk: LICS 2021 - Symposium on Logic in Computer Science,
Rom;
2021-06-29
- 2021-07-02; in: "Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science",
(2021),
ISBN: 978-1-6654-4895-6;
1
- 13.
English abstract:
The concept of bounded expansion provides a robust
way to capture sparse graph classes with interesting algorithmic
properties. Most notably, every problem definable in first-order
logic can be solved in linear time on bounded expansion graph
classes. First-order interpretations and transductions of sparse
graph classes lead to more general, dense graph classes that
seem to inherit many of the nice algorithmic properties of their
sparse counterparts.
In this work we introduce lacon- and shrub-decompositions
and use them to characterize transductions of bounded expansion
graph classes and other graph classes. If one can efficiently
compute sparse shrub- or lacon-decompositions of transductions
of bounded expansion classes then one can solve every problem
definable in first-order logic in linear time on these classes.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1109/LICS52264.2021.9470680
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_299558.pdf
Created from the Publication Database of the Vienna University of Technology.