An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO)

We design the first efficient parallel algorithm for computing Minimal Elimination Ordering (MEO) of an arbitrary graph.The algorithm works in O(log(superscript 3)n) parallel time and O(nm) processors on a CRCW PRAM, for an n-vertex, m-edge graph, and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of Rose, Tarjan and Lueker.The MEO Problem for arbitrary graphs arises in a number of combinatorial optimization problems, as well as in database applications, scheduling problems, and the sparse Gaussian elimination of symmetric matrices. It was believed before to be inherently sequential and strongly resisting sublinear parallel time (sublinear sequential storage) algorithms.As an application, this paper gives the first efficient parallel solutions to the problem of Minimal Fill-In for arbitrary graphs (and connected combinatorial problems, cf. [RTL 76],[Ta 85]), and to the problem of the Gaussian elimination of sparse symmetric matrices [Ro 70], [Ro 73]. (The problem of computing Minimum Fill-In is known to be NP-complete [Ya 81]). It gives also an alternative to [GM 87] efficient parallel algorithm for computing Breadth-First Search (BFS) trees in arbitrary graphs using O(nm) processors on a CRCW PRAM.The method of solution involves a development of new techniques for solving connected minimal set system problem, and combining it with some new divide-and-conquer methods.

ICSI Technical Report TR-89-024

Technical Report