6 papers
The directed temporal exploration problem
Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang +1
We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of suffices to guarantee the existence of a temporal exploration on always-unilate…
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…
Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani +1
In the Vertex Disjoint Paths with Congestion problem, the input consists of a digraph , an integer and pairs of vertices , and the task is to find a set of p…
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…
Directed Ear Anonymity
Marcelo Garlet Milani
We define and study a new structural parameter for directed graphs, which we call \emph{ear anonymity}. Our parameter aims to generalize the useful properties of \emph{funnels} to…
A Polynomial Kernel for Funnel Arc Deletion Set
Marcelo Garlet Milani
In Directed Feeback Arc Set (DFAS) we search for a set of at most arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized comple…