Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Matthew Andrews:

TR07-113 | 15th November 2007
Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

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 >>>

ISSN 1433-8092 | Imprint