Parallel Algorithms for River Routing.

Abstract

We develop fast parallel algorithms for several river routing problems. These algorithms are efficient in the sense that the number of processors used is O(n), where n is the size of the input. Two parallel models of computation are considered: the CREW PRAM model and the two-dimensional mesh of processors model. Our algorithms run in time O(log n) or O(log^2 n) on the first model and in time O(SQRT n) on the second model. Optimal algorithms are developed for several subproblems that are interesting on their own. One such subproblem is to determine the contours of the union of sets of contours within a rectilinear polygon.