Efficient algorithms for finding disjoint paths in grids

Abstract

The reconfiguration problem on VLSI/WSI processor arrays in the presence of faulty processors can be stated as the following integral multi-source routing problem: Given a set of N nodes (faulty processors or sources) in an m×n rectangular grid where m, n≤N, the problem to be solved is to connect the N nodes to distinct nodes at the grid boundary using a set of `disjoint' paths. This problem can be referred to as an escape problem which can be solved trivially in O(mnN) time. By exploiting all the properties of the network, planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the grid from O(mn) to O(√mnN) and solve the problem in O(d√mnN), where d is the maximum number of disjoint paths found, for both the edge-disjoint and vertex-disjoint cases. In the worst case, d, m, n are O(N) and the result is O(N2.5). Note that this routing problem can also be solved with the same time complexity even if the disjoint paths have to be ended at another set of N nodes (sinks) in the grid instead of the grid boundary.