Julia Chuzhoy, Sanjeev Khanna

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed ...
more >>>