4 papers · 1 filter
A directed flat wall theorem excluding a crossrow grid
Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The graph minor project contains the most influential results in recent undirected graph theory research. There has been progress in recent years in generalising some of their resu…
Optimal Bounds for the k-Disjoint Paths Problem
Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer +2
The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Path…
Directed treewidth is closed under taking butterfly minors
Gunwoo Kim, Meike Hatzel, Stephan Kreutzer
Butterfly minors are a generalisation of the minor containment relation for undirected graphs to directed graphs. Many results in directed structural graph theory use this notion a…
Generating strongly 2-connected digraphs
Meike Hatzel, Stephan Kreutzer, Evangelos Protopapas +3
We prove that there exist four operations such that given any two strongly -connected digraphs and where is a butterfly-minor of , there exists a sequence $D_0,\d…