32 citations · 59 across the 26 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011
Approximation Algorithms and Hardness of the k-Route Cut Problem
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan +1
We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivit…
cs.DS2011
Routing in Undirected Graphs with Constant Congestion
Julia Chuzhoy
Given an undirected graph G=(V,E), a collection (s_1,t_1),...,(s_k,t_k) of k source-sink pairs, and an integer c, the goal in the Edge Disjoint Paths with Congestion problem is to…