Routing in Undirected Graphs with Constant Congestion

2011/07/13 by Julia Chuzhoy, Chuzhoy, Julia · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1107.2554

openalex publication_date 2011/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given an undirected graph G=(V,E), a collection (s₁,t₁),...,(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 Ω(OPT/\polylog 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/\polylog 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.

Cited by

• O(log n)-Approximation Algorithms for Bipartiteness Ratio
• SoK: Automated Vulnerability Repair: Methods, Tools, and Assessments

Related

• A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
• Maximum Edge-Disjoint Paths in k-sums of Graphs
• Routing with Congestion in Acyclic Digraphs
• On Routing Disjoint Paths in Bounded Treewidth Graphs