Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with network routing:
TR06-109 | 29th August 2006
Julia Chuzhoy, Sanjeev Khanna

Hardness of Directed Routing with Congestion

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

TR06-141 | 22nd November 2006
Venkatesan Guruswami, Kunal Talwar

Hardness of Low Congestion Routing in Directed Graphs

We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>

ISSN 1433-8092 | Imprint