[Zurück]

J. Dreier:
"Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes";
Vortrag: LICS 2021 - Symposium on Logic in Computer Science, Rom; 29.06.2021 - 02.07.2021; in: "Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science", (2021), ISBN: 978-1-6654-4895-6; S. 1 - 13.

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.

http://dx.doi.org/10.1109/LICS52264.2021.9470680

https://publik.tuwien.ac.at/files/publik_299558.pdf