23 citations · 110 across the 25 of their papers we have counts for
3 papers · 2 filters
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…