1 citations · 2 across the 4 of their papers we have counts for
5 papers
Decomposition into two trees with orientation constraints
Olivier Durand de Gevigney
We prove that deciding whether the edge set of a graph can be partitionned into two spanning trees with orientation constraints is NP-complete. If P NP then this disproves a…
On Frank's conjecture on k-connected orientations
Olivier Durand de Gevigney
We disprove a conjecture of Frank stating that each weakly 2k-connected has a k-vertex-connected orientation. For k at least 3, we also prove that the problem of deciding whether a…
On (2k,k)-connected graphs
Olivier Durand de Gevigney, Zoltán Szigeti
A graph G is called (2k, k)-connected if G is 2k-edge-connected and G-v is k-edge-connected for every vertex v. The study of (2k, k)-connected graphs is motivated by a conjecture o…
Basic Packing of Arborescences
Olivier Durand de Gevigney, Viet-Hang Nguyen, Zoltán Szigeti
We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rooted-tree decompositions with matroid constraints. Our result characterises digraphs h…
Directed paths on a tree: coloring, multicut and kernel
Olivier Durand de Gévigney, Frédéric Meunier, Christian Popa +2
In the present paper, we study algorithmic questions for the arc-intersection graph of directed paths on a tree. Such graphs are known to be perfect (proved by Monma and Wei in 198…