In a rectangular grid, given two sets of nodes, L (sources) and T (sinks), of size N/2 each, the disjoint paths (DP) problem is to connect as many nodes in L to the nodes in T 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 L can be connected to any node in T. Although in general the sizes of L and T do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in L and T. 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(N-2) to O(N-1.5) and solve the problem in O(N-2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N-3) time. (C) 2000 Academic Press. [References: 24]
展开▼
