Routing in Undirected Graphs with Constant Congestion
Chuzhoy, Julia
Original · EN
Given an undirected graph G=(V,E), a collection (s₁,t₁),...,(sₖ,tₖ) 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 Ω(OPT/ 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 Ω(OPT/ n) pairs required congestion (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ᵒ⁽¹/ᶜ⁾ pairs.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.