23 citations · 110 across the 25 of their papers we have counts for
13 papers · 1 filter
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
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…
Algorithmic Properties of Sparse Digraphs
Stephan Kreutzer, Patrice Ossona de Mendez, Roman Rabinovich +1
The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expan…
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
Nowhere dense classes of graphs are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a character…
The Generalised Colouring Numbers on Classes of Bounded Expansion
Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich +1
The generalised colouring numbers , , and were introduced by Kierstead and Yang as generalisations of the usual colouring…
The Erdos-Posa Property for Directed Graphs
Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Stephan Kreutzer +1
A classical result by Erdos and Posa states that there is a function such that for every , every graph contains pairwise vertex…
The Directed Grid Theorem
Ken-ichi Kawarabayashi, Stephan Kreutzer
The grid theorem, originally proved by Robertson and Seymour in Graph Minors V in 1986, is one of the most central results in the study of graph minors. It has found numerous appli…
DAG-width is PSPACE-complete
Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich
Berwanger et al. show that for every graph of size and DAG-width there is a DAG decomposition of width and size . This gives a polynomial time algorithm f…
Directed Width Measures and Monotonicity of Directed Graph Searching
Łukasz Kaiser, Stephan Kreutzer, Roman Rabinovich +1
We consider generalisations of tree width to directed graphs, that attracted much attention in the last fifteen years. About their relative strength with respect to "bounded width…
Directed Nowhere Dense Classes of Graphs
Stephan Kreutzer, Siamak Tazari
We introduce the concept of shallow directed minors and based on this a new classification of classes of directed graphs which is diametric to existing directed graph decomposition…
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
Stephan Kreutzer, Siamak Tazari
Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that…
Digraph Decompositions and Monotonicity in Digraph Searching
Stephan Kreutzer, Sebastian Ordyniak
We consider monotonicity problems for graph searching games. Variants of these games - defined by the type of moves allowed for the players - have been found to be closely connecte…