From Parallel To Sequential: Keeping Optimality In Algorithms

In this paper we first give a survey that describes the reductions between several fundamental parallel graph problems. Then, we examine the possibility of designing simple and practical sequential algorithms from parallel ones. Interestingly enough, we show how to design fast (in fact optimal) sequential algorithms from the optimal parallel algorithms for a graph theoretic problem that arizes often in many areas including Economics and Operations Research. In particular, we give two optimal algorithms that solve the vertex updating for a minimum spanning tree problem. Finally, we show how these algorithms can be used to obtain incremental algorithms for computing the minimum spanning tree (MST) of a graph. The MST algorithms are optimal for dense graphs. 1 Introduction Parallelizing Sequential Algorithms. Ever since the first attempt of building parallel machines, researchers have looked into the existing sequential algorithms in an effort to parallelize them efficiently. Unfortunate..