Showing 2018Show all
3 papers · 1 filter
cs.LO2018
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…
cs.DM2018
First-order interpretations of bounded expansion classes
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil +4
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-che…
cs.DM2018
Parameterized circuit complexity of model checking first-order logic on sparse structures
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs with effectively bounded expansion, given a first-order sentence and an -element structure whose Gaifman graph belon…