3 citations · 6 across the 3 of their papers we have counts for
5 papers
Modules and PQ-trees in Robinson spaces
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
A Robinson space is a dissimilarity space on points for which there exists a compatible order, {\it i.e.} a total order on such that implies that $d(x,y…
Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators
Guyslain Naves, Bruce Shepherd, Henry Xia
Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i)…
When Do Gomory-Hu Subtrees Exist?
Guyslain Naves, F. Bruce Shepherd
Gomory-Hu (GH) Trees are a classical sparsification technique for graph connectivity. It is one of the fundamental models in combinatorial optimization which also continually finds…
Maximum Edge-Disjoint Paths in -sums of Graphs
Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd
We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow ba…
The graphs with the max-Mader-flow-min-multiway-cut property
Guyslain Naves, Vincent Jost
We are given a graph , an independant set of \emph{terminals}, and a function . We want to know if the maximum -packing of v…