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

✍ Scribed by Jon Kleinberg; Éva Tardos

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 512 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1579

✦ Synopsis

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 alloptical networks. In this paper we provide O(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 an O(log n)-approximation to the maximum number of terminal pairs that can be simultaneously connected via edge-disjoint paths, and an O(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 an O(log 2 n)-approximation for the special case of the mesh obtained independently by Aumann and Rabani. For both problems the O(log n)-approximation is a consequence of an O(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.