|
|||||
|
|
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs |
|
| Authors: | Matthew Andrews Julia Chuzhoy Venkatesan Guruswami Sanjeev Khanna Kunal Talwar Lisa Zhang |
| Institution: | 1. Bell Laboratories, Lucent Technologies, Murray Hill, NJ, USA 2. Toyota Technological Institute, Chicago, IL, 60637, USA 3. Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 15213, USA 4. Dept. of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, 19104, USA 5. Microsoft Research, Silicon Valley Campus, Mountain View, CA, 94043, USA |
| Abstract: | 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 through any edge in the graph. When c = 1, the problem is simply referred to as the Edge-Disjoint Paths (EDP) problem. In this paper, we study the hardness of EDPwC in undirected graphs. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |