Applying parallel computation algorithms in the design of serial algorithms
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 399-408
- https://doi.org/10.1109/sfcs.1981.11
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.Keywords
This publication has 12 references indexed in Scilit:
- A Shifting Algorithm for Min-Max Tree PartitioningJournal of the ACM, 1982
- Max-Min Tree PartitioningJournal of the ACM, 1981
- Generating and searching sets induced by networksLecture Notes in Computer Science, 1980
- Combinatorial Optimization with Rational Objective FunctionsMathematics of Operations Research, 1979
- A Fast Selection Algorithm and the Problem of Optimum Distribution of EffortJournal of the ACM, 1979
- New Parallel-Sorting SchemesIEEE Transactions on Computers, 1978
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978
- Minimal ratio spanning treesNetworks, 1977
- Finding Minimum Spanning TreesSIAM Journal on Computing, 1976
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975