Efficient algorithms for disjoint paths problems in grids
(Uncorrected OCR) Abstract of thesis entitled "Efficient Algorithms for Disjoint Paths Problems in Grids" submitted by Chan Wun Tat for the degree of Doctor of Philosophy at The University of Hong Kong in August 1999 Finding disjoint paths in a graph is a fundamental problem in computer science. This thesis focuses on the problem when the underlying graph is a two-dimensional grid. Given a set of sources and a set of sinks in the grid, we want to find a set of disjoint (vertex-disjoint or edge-disjoint) paths in which each path connects a distinct source to a distinct sink and there is no predefined pairing between the sources and the sinks. This disjoint paths problem has applications in many fields, such as the reconfiguration of faulty processors array, point-to-point delivery problems, and routing in Printed Circuit Board (PCB), Very Large Scale Integration (VLSI) and Multi-Chip Module (MCM). Our first contribution is an 0(v) time procedure which preprocesses the input grid of unlimited size to a grid of size n with v < n < 4v2 where v is the number of sources and sinks. The conventional approach solves the problem by reducing it to a maximum flow problem and runs in 0(min(m>, n3//2)) time. We adopt and improve this approach for both the edge-disjoint and the vertex-disjoint path cases. The improvement mainly comes from (1) a compression on the source-and-sink-free sub-grids such that the size of the grid is reduced to 0(y/rw) and (2) an extended use of the layered network technique in our compressed network. Our algorithm runs in 0(n3/'4t)3/'4) time which speeds up by a factor of (^/v) when n is 0(v2). We consider a special case of the problem where all sinks lie on the grid boundary and the sources and the sinks are to be connected by edge-disjoint paths. For this problem, we take a different approach based on a condition for which the problem is solvable, namely all subgrids must contain no more sources than outlets. Two algorithms are presented with one verifying the condition and another one constructing the edge-disjoint paths, both in 0(y2) time. We also design algorithms in finding the vertex-disjoint paths around a rectangle for the sources and the sinks on the rectangle boundary. Our algorithms take 0(vlogv) time to find the paths in which the length of the longest path is minimized and take 0(v2) time to find the paths with minimum total path length.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:paths and cycles graph theory computer algorithms
Date of Publication:01/01/2000