4 papers
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…
On the number of types in sparse graphs
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs which is nowhere dense, as defined by Nesetril and Ossona de Mendez, and for every first order formula , whe…
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…