Edge Disjoint Paths in Moderately Connected Graphs
Edge Disjoint Paths in Moderately Connected Graphs
复制标题
中等连通图中的边不相交路径
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Shuheng Zhou
中科院分区：
文献类型：
--
作者：
Satish Rao;Shuheng Zhou
研究了无向图中的边不相交路径问题：给定一个有n个结点的图G和一个终端对集合${mathcal T}$，用互边不相交的路径连接尽可能多的终端对。这导致了各种经典的NP-完全问题，对于这些问题的逼近性还没有得到很好的理解。我们给出了一般图中连通性适度限制的无向最小割问题的多对数逼近算法，我们要求G的全局最小割为Ω(Log5n)。以前，常数或多对数近似算法已知用于具有平行边、扩展器、网格和网格状图形的树，以及最近的偶数度平面图。这些图要么具有特殊的结构(例如，它们排除了子项)，要么存在大量不相交的短路径。我们的算法扩展了以前的技术，因为它适用于具有大直径和渐近大子数的图。
We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set ${mathcal T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximability is not well understood. We show a polylogarithmic approximation algorithm for the undirected EDP problem in general graphs with a moderate restriction on graph connectivity; we require the global minimum cut of G to be Ω(log5n). Previously, constant or polylogarithmic approximation algorithms were known for trees with parallel edges, expanders, grids and grid-like graphs, and most recently, even-degree planar graphs. These graphs either have special structure (e.g., they exclude minors) or there are large numbers of short disjoint paths. Our algorithm extends previous techniques in that it applies to graphs with high diameters and asymptotically large minors.