Efficient algorithms for finding disjoint paths in grids
Wun-Tat Chan, Francis Y. L. Chin · Symposium on Discrete Algorithms · 1997
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 am m x n rectangular grid where m, n {le} N, the problem to be solved is to connect the N nodes to distinct nodes at the grid boundary using a set of {open_quotes}disjoint{close_quotes} 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({radical}mnN) and solve the problem in O(d{radical}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(N{sup 2.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.