Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-13
Computer Science
Data Structures and Algorithms
Scientific paper
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 connect maximum possible number of the source-sink pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed c. We show an efficient randomized algorithm to route $\Omega(OPT/\poly\log k)$ source-sink pairs with congestion at most 14, where OPT is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The best previous algorithm that routed $\Omega(OPT/\poly\log n)$ pairs required congestion $\poly(\log \log n)$, and for the setting where the maximum allowed congestion is bounded by a constant c, the best previous algorithms could only guarantee the routing of $OPT/n^{O(1/c)}$ pairs.
No associations
LandOfFree
Routing in Undirected Graphs with Constant Congestion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Routing in Undirected Graphs with Constant Congestion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing in Undirected Graphs with Constant Congestion will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165860