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

作者：Kawarabayashi Ken Ichi; Kobayashi Yusuke^*

来源：ACM Transactions on Algorithms, 2013, 9(2): 16.

DOI：10.1145/2438645.2438648

• Edge-disjoint paths
• approximation algorithm
• Eulerian graph
• 4-edge-connected graph

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.

• 出版日期2013-3