5 papers · 1 filter
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Ordered graphs of bounded twin-width
Pierre Simon, Szymon Toruńczyk
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular…
Aggregate Queries on Sparse Databases
Szymon Toruńczyk
We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framewor…
Progressive Algorithms for Domination and Independence
Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz +1
We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. We identify two m…
The MSO+U theory of (N, <) is undecidable
Mikołaj Bojańczyk, Paweł Parys, Szymon Toruńczyk
We consider the logic MSO+U, which is monadic second-order logic extended with the unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets ho…