Edge-Disjoint Paths in Planar Graphs with Constant Congestion
| Autor: | F. Bruce Shepherd, Chandra Chekuri, Sanjeev Khanna |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
General Computer Science General Mathematics Disjoint sets Binary logarithm Upper and lower bounds Omega Multi-commodity flow problem Planar graph Constant factor Combinatorics symbols.namesake Graph Node Flow (mathematics) symbols Node (circuits) Relaxation (approximation) Decomposition method (constraint satisfaction) Constant (mathematics) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | STOC |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/060674442 |
| Popis: | We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs s1t1, s2t2, ..., sktk, the goal is to maximize the number of pairs that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap. Motivated by this, we consider solutions with small constant congestion c > 1; that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems.In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation.We also study limitations on the approximation that can be achieved by a well-linked decomposition. For general graphs we show a lower bound of Ω(log n). For planar graphs we describe instances that suggest a super-constant lower bound. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|