4 citations · 17 across the 11 of their papers we have counts for
15 papers
Uncrossed Multiflows and Applications to Disjoint Paths
Chandra Chekuri, Guyslain Naves, Joseph Poremba +1
A multiflow in a planar graph is uncrossed if its support paths do not cross. Recently such flows have played a role in approximation algorithms for maximum disjoint paths in "full…
The steady-states of splitter networks
Basile Couëtoux, Bastien Gastaldi, Guyslain Naves
We introduce splitter networks, which abstract the behavior of conveyor belts found in the video game Factorio. Based on this definition, we show how to compute the steady-state of…
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…
A simple and optimal algorithm for strict circular seriation
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
Recently, Armstrong, Guzmán, and Sing Long (2021), presented an optimal time algorithm for strict circular seriation (called also the recognition of strict quasi-circular…
Modules in Robinson Spaces
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
A Robinson space is a dissimilarity space (i.e., a set of size and a dissimilarity on ) for which there exists a total order on such that imp…
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…
Packing and covering with balls on Busemann surfaces
Victor Chepoi, Bertrand Estellon, Guyslain Naves
In this note we prove that for any compact subset of a Busemann surface (in particular, for any simple polygon with geodesic metric) and any positive number…
Balancing lists: a proof pearl
Guyslain Naves, Arnaud Spiwack
Starting with an algorithm to turn lists into full trees which uses non-obvious invariants and partial functions, we progressively encode the invariants in the types of the data, r…
Isometric embedding of Busemann surfaces into
Jérémie Chalopin, Victor Chepoi, Guyslain Naves
In this paper, we prove that any non-positively curved 2-dimensional surface (alias, Busemann surface) is isometrically embeddable into . As a corollary, we obtain that all pl…
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…
Congestion in planar graphs with demands on faces
Guyslain Naves, Christophe Weibel
We give an algorithm to route a multicommodity flow in a planar graph with congestion , where is the maximum number of terminals on the boundary of a face, when…
On disjoint paths in acyclic planar graphs
Guyslain Naves
We give an algorithm with complexity for the integer multiflow problem on instances with an acyclic planar digraph and Eulerian. Here, $…
The hardness of routing two pairs on one face
Guyslain Naves
We prove the NP-completeness of the integer multiflow problem in planar graphs, with the following restrictions: there are only two demand edges, both lying on the infinite face of…