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 条
  • [31] Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
    Guruswami, V
    Khanna, S
    Rajaraman, R
    Shepherd, B
    Yannakakis, M
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (03) : 473 - 496
  • [32] The Edge-Disjoint Path Problem on Random Graphs by Message-Passing
    Altarelli, Fabrizio
    Braunstein, Alfredo
    Dall'Asta, Luca
    De Bacco, Caterina
    Franz, Silvio
    PLOS ONE, 2015, 10 (12):
  • [33] On the maximum disjoint paths problem on edge-colored graphs
    Wu, Bang Ye
    DISCRETE OPTIMIZATION, 2012, 9 (01) : 50 - 57
  • [34] An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    OPERATIONS RESEARCH, 2017, 65 (04) : 1043 - 1061
  • [35] Terminal-pairability in complete bipartite graphs with non-bipartite demands Edge-disjoint paths in complete bipartite graphs
    Colucci, Lucas
    Erdos, Peter L.
    Gyori, Ervin
    Mezei, Tamas Robert
    THEORETICAL COMPUTER SCIENCE, 2019, 775 : 16 - 25
  • [36] Many-to-many edge-disjoint paths in (n, k)-enhanced hypercube under three link-faulty hypotheses
    Liu, Hongxi
    Zhang, Mingzu
    Xu, Xiaowei
    THEORETICAL COMPUTER SCIENCE, 2023, 957
  • [37] A 2√2k-approximation algorithm for minimum power k edge disjoint st-paths
    Nutov, Zeev
    INFORMATION PROCESSING LETTERS, 2025, 188
  • [38] A Simpler and Parallelizable O(√log n)-approximation Algorithm for SPARSEST CUT
    Kolmogorov, Vladimir
    PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024, 2024, : 403 - 414
  • [39] A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
    Joel Antonio Trejo-Sánchez
    Francisco A. Madera-Ramírez
    José Alberto Fernández-Zepeda
    José Luis López-Martínez
    Alejandro Flores-Lamas
    Optimization Letters, 2023, 17 : 1435 - 1454
  • [40] A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
    Trejo-Sanchez, Joel Antonio
    Madera-Ramirez, Francisco A.
    Alberto Fernandez-Zepeda, Jose
    Luis Lopez-Martinez, Jose
    Flores-Lamas, Alejandro
    OPTIMIZATION LETTERS, 2023, 17 (06) : 1435 - 1454
12345