Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Nimrod Megiddo · Journal of the ACM · 1983
The goal of this paper is to point out that analyses of parallelism m computational problems have practical implications even when mult~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 efficsent serial algorithm for another problem A unified framework for cases like this is presented.Particular cases, which axe discussed in this paper, provide motivation for examining parallelism in sorting, selecuon, minimum-spanning-tree, shortest route, max-flow, and matrix multiplication problems, as well as in scheduling and locational problems.