Disjoint Paths in Densely Embedded Graphs

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 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 asymptptically optimal O(log n)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 B. Awerbuch et al (1994).

Authors

• Jon M. Kleinberg
• Éva Tardos

Keywords

• Routing
• Approximation algorithms
• High-speed networks
• Intelligent networks
• Multiprocessor interconnection networks
• Tree graphs
• NP-complete problem
• High speed optical techniques
• Optical fiber networks
• Operations research
• Enclosure
• Multiple Edges
• Extension Of Theorem
• Pair Of Nodes
• Algorithm For Problem
• Online Algorithm
• Class Of Graphs
• High-speed Network
• Sufficient Conditions
• Pathfinding
• Combination Of Algorithms
• Simulated Networks
• Approximate Ratio
• Routing Problem
• Constant Probability
• Routing Algorithm
• Compact Surface
• Proof Sketch
• Short Connections
• Additional Notation
• Competitive Ratio
• Terminal Pair