Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks

摘要

We consider the problem of connecting distinguished terminal pairs in a graph via edge-disjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers discussing applications to admission control in high-speed networks and to routing in all- optical networks. In this paper we provideO(log n)-approximation algorithms for two natural optimization versions of this problem for the class of nearly Eulerian, uniformly high-diameter planar graphs, which includes two-dimensional meshes and other common planar interconnection networks. We give anO(log n)-approximation to the maximum number of terminal pairs that can be simultaneously connected via edge-disjoint paths, and anO(log n)-approximation to the minimum number of wavelengths needed to route a collection of terminal pairs in the “optical routing” model considered by Raghavan, Upfal, and others. The latter result improves on anO(log2 n)-approximation for the special case of the mesh obtained independently by Aumann and Rabani. For both problems theO(log n)-approximation is a consequence of anO(1)-approximation for the special case when all terminal pairs are roughly the same distance apart. Our algorithms make use of a number of new techniques, including the construction of a “crossbar” structure in any nearly Eulerian planar graph, and develops some connections with classical matroid algorithms.