5 papers · 1 filter
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we…
Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 1996, Reed, Robertson, Seymour and Thomas [Combinatorica 1996] proved Younger's Conjecture, which states that, for all directed graphs , there exists a function such that…
Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 2015, Kawarabayashi and Kreutzer proved the Directed Grid Theorem - the generalisation of the well-known Excluded Grid Theorem to directed graphs - confirming a conjecture by Re…
Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that for every surface , the class of Eulerian directed graphs that are Eulerian embeddable into (in particular they have degree at most ) is well-quasi-ordere…
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…