Showing 2024Show all
3 papers · 1 filter
math.CO2024
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…
cs.DM2024
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…
cs.CC2024
Edge-Disjoint Paths in Eulerian Digraphs
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
Disjoint paths problems are among the most prominent problems in combinatorial optimization. The edge- as well as vertex-disjoint paths problem, are NP-complete on directed and und…