Applying parallel computation algorithms in the design of serial algorithms

Abstract

The goal of this paper is to point out that analyses of parallelism in computational problems have practical implications even when multi-processor machines are not available. This is true because, in many cases, a good parallel algorithm for one problem may turn out to be useful for designing an efficient serial algorithm for another problem. A unified framework for cases like this is presented. Particular cases, which are discussed in this paper, provide motivation for examining parallelism in problems like sorting, selection, minimum-spanning-tree, shortest route, maxflow, matrix multiplication, as well as scheduling and locational problems.