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 条

[41] On the 1.375-Approximation Algorithm for Sorting by Transpositions in O(n log n) Time
Cunha, Luis Felipe I.
Kowada, Luis Antonio B.
Hausen, Rodrigo de A.
de Figueiredo, Celina M. H.
ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, 2013, 8213 : 126 - 135
[42] AN O(log2 k)-APPROXIMATION ALGORITHM FOR THE k-VERTEX CONNECTED SPANNING SUBGRAPH PROBLEM
Fakcharoenphol, Jittat
Laekhanukit, Bundit
SIAM JOURNAL ON COMPUTING, 2012, 41 (05) : 1095 - 1109
[43] An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
Koenemann, Jochen
Sadeghian, Sina
Sanita, Laura
2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 568 - 577
[44] An O(log2 k)-Approximation Algorithm for the k-Vertex Connected Spanning Subgraph Problem
Fakcharoenphol, Jittat
Laekhanukit, Bundit
STOC'08: PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING, 2008, : 153 - 158
[45] A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
Takazawa, Kenjiro
INFORMATION PROCESSING LETTERS, 2016, 116 (09) : 550 - 553
[46] An O(k3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
Chuzhoy, Julia
Khanna, Sanjeev
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, : 437 - 441
[47] An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity
Qiao, Hengji
Zhang, Mingzu
Ma, Wenhuan
Yang, Xing
PARALLEL PROCESSING LETTERS, 2023, 33 (01N02)
[48] A Randomized O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {O}(\log n)$$\end{document}-Competitive Algorithm for the Online Connected Facility Location Problem
Mário César San Felice
David P. Williamson
Orlando Lee
Algorithmica, 2016, 76 (4) : 1139 - 1157

← 1 2 3 4 5 →