
On the discrepancy of set systems definable in sparse graph classes
Discrepancy is a natural measure for the inherent complexity of set syst...
read it

Twinwidth and permutations
Inspired by a width invariant defined on permutations by Guillemot and M...
read it

Recursive Backdoors for SAT
A strong backdoor in a formula ϕ of propositional logic to a tractable c...
read it

Constant round distributed domination on graph classes with bounded expansion
We show that the dominating set problem admits a constant factor approxi...
read it

Towards an arboretum of monadically stable classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
read it

Rankwidth meets stability
We study two notions of being wellstructured for classes of graphs that...
read it

Elimination distance to bounded degree on planar graphs
We study the graph parameter elimination distance to bounded degree, whi...
read it

Regular partitions of gentle graphs
Szemeredi's Regularity Lemma is a very useful tool of extremal combinato...
read it

Linear rankwidth meets stability
Classes with bounded rankwidth are MSOtransductions of trees and classe...
read it

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of an optimization problem Q the input is a...
read it

Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
The notion of nowhere dense graph classes was introduced by Nešetřil and...
read it

Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Classes with bounded rankwidth are MSOtransductions of trees and classe...
read it

Parameterized Distributed Complexity Theory: A logical approach
Parameterized complexity theory offers a framework for a refined analysi...
read it

ModelChecking on Ordered Structures
We study the modelchecking problem for first and monadic secondorder ...
read it

Progressive Algorithms for Domination and Independence
We consider a generic algorithmic paradigm that we call progressive expl...
read it

Firstorder interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
read it

Kernelization and approximation of distancer independent sets on nowhere dense graphs
For a positive integer r, a distancer independent set in an undirected ...
read it

Polynomial bounds for centered colorings on proper minorclosed graph classes
For p∈N, a coloring λ of the vertices of a graph G is pcentered if for ...
read it

Greedy domination on bicliquefree graphs
The greedy algorithm for approximating dominating sets is a simple metho...
read it

Parameterized circuit complexity of model checking firstorder logic on sparse structures
We prove that for every class C of graphs with effectively bounded expan...
read it

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform QuasiWideness
The notions of bounded expansion and nowhere denseness not only offer ro...
read it
Sebastian Siebertz
is this you? claim profile