An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs

被引：10
|
作者：
Kawarabayashi, Ken-Ichi [1 ]
Kobayashi, Yusuke [2 ]
机构：
[1] Res Org Informat & Syst, Natl Inst Informat, Chiyoda Ku, Tokyo 1018430, Japan
[2] Univ Tokyo, Bunkyo Ku, Tokyo 1138656, Japan
来源：
ACM TRANSACTIONS ON ALGORITHMS | 2013年 / 9卷 / 02期
基金：
日本学术振兴会;
关键词：
Edge-disjoint paths; approximation algorithm; Eulerian graph; 4-edge-connected graph; MULTICOMMODITY FLOWS; APPROXIMATION ALGORITHMS; CONGESTION; HARDNESS;
D O I：
10.1145/2438645.2438648
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this article, we study an approximation algorithm for the maximum edge-disjoint paths problem. In this problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be connected by edge-disjoint paths. We give an O(log n)-approximation algorithm for the maximum edge-disjoint paths problem when an input graph is either 4-edge-connected planar or Eulerian planar. This improves an O(log(2) n)-approximation algorithm given by Kleinberg [2005] for Eulerian planar graphs. Our result also generalizes the result by Chekuri et al. [2004, 2005] who gave an O(log n)-approximation algorithm for the maximum edge-disjoint paths problem with congestion two when an input graph is planar.
引用
收藏
页数：13
相关论文
共 48 条
  • [1] An O(log n)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Gr
    Kawarabayashi, Ken-ichi
    Kobayashi, Yusuke
    APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2010, 6302 : 274 - +
  • [2] AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS
    Huang, Chien-Chung
    Mari, Mathieu
    Mathieu, Claire
    Schewior, Kevin
    Vygen, Jens
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 752 - 769
  • [3] The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
    Kawarabayashi, Ken-ichi
    Kobayashi, Yusuke
    COMBINATORICA, 2015, 35 (04) : 477 - 495
  • [4] EDGE-DISJOINT PATHS IN PLANAR GRAPHS WITH CONSTANT CONGESTION
    Chekuri, Chandra
    Khanna, Sanjeev
    Shepherd, F. Bruce
    SIAM JOURNAL ON COMPUTING, 2009, 39 (01) : 281 - 301
  • [5] A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
    Chuzhoy, Julia
    Li, Shi
    JOURNAL OF THE ACM, 2016, 63 (05)
  • [6] Maximum edge-disjoint paths in planar graphs with congestion 2
    Seguin-Charbonneau, Loic
    Shepherd, F. Bruce
    MATHEMATICAL PROGRAMMING, 2021, 188 (01) : 295 - 317
  • [7] Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
    Seguin-Charbonneau, Loic
    Shepherd, F. Bruce
    2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 200 - 209
  • [8] An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
    Kawarabayashi, Ken-Ichi
    Kobayashi, Yusuke
    ACM TRANSACTIONS ON ALGORITHMS, 2016, 13 (01)
  • [9] A genetic algorithm for the maximum edge-disjoint paths problem
    Hsu, Chia-Chun
    Cho, Hsun-Jung
    NEUROCOMPUTING, 2015, 148 : 17 - 22
  • [10] On the complexity of the planar directed edge-disjoint paths problem
    Müller, D
    MATHEMATICAL PROGRAMMING, 2006, 105 (2-3) : 275 - 288
12345