4 citations · 17 across the 11 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
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…
cs.DS2020
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)…
cs.DS2014
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…