Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids

Abstract

In a rectangular grid, given two sets of nodes, script capital L sign (sources) and script T sign (sinks), of size N/2 each, the disjoint paths (DP) problem is to connect as many nodes in script capital L sign to the nodes in script T sign using a set of "disjoint" paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in script capital L sign can be connected to any node in script T sign. Although in general the sizes of script capital L sign and script T sign do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in script capital L sign and script T sign. We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N2) to U(N1.5) and solve the problem in O(N2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N3) time. © 2000 Academic Press.