3 citations · 3 across the 2 of their papers we have counts for
3 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…
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)…
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…