Parallel Algorithms for River Routing.

Loading...
Thumbnail Image

Files

TR_87-103.pdf (938.28 KB)
No. of downloads: 419

Publication or External Link

Date

1987

Advisor

Citation

DRUM DOI

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.

Notes

Rights