Disjoint Paths in Densely Embedded Graphs (Preprint)
Abstract
We consider the following maximum disjoint paths problem (MDPP). We are given a large network, and pairs of nodes that wish to communicate over paths through the network -- the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem has been brought into focus recently in papers discussing applications to routing in high-speed networks, where the current lack of understanding of the MDPP is an obstacle to the design of practical heuristics. We consider the class of densely embedded, nearly-Eulerian graphs, which includes the two-dimensional mesh and many other planar and locally planar interconnection networks. We obtain a constant-factor approximation algorithm for the maximum disjoint paths problem for this class of graphs; this improves on an O(log n)-approximation for the special case of the two-dimensional mesh due to Aumann-Rabani and the authors. For networks that are not explicitly required to be "high-capacity," this is the first constant-factor approximation for the MDPP in any class of graphs other than trees. We also consider the MDPP in the on-line setting, relevant to applications in which connection requests arrive over time and must be processed immediately. Here we obtain an asymptotically optimal O(log )-competitive on-line algorithm for the same class of graphs; this improves on an O(log n log log n)-competitive algorithm for the special case of the mesh due to Awerbuch, Gawlick, Leighton, and Rabani.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1995
- Accession Number
- ADA640222
Entities
People
- Jon Kleinberg
- Éva Tardos
Organizations
- Massachusetts Institute of Technology