An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph

The first efficient parallel algorithm for computing minimal elimination ordering (MEO) of an arbitrary graph is designed. The algorithm works in O(log/sup 3/n) parallel time and O(nm) processors on a concurrent-read-concurrent-write parallel random-access machine (CRCW PRAM) for an n-vertex, m-edge graph and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of D. Rose et. al. (SIAM J. Comput., vol.5, p.266-83, 1976). As an application, the first efficient parallel solution to the problem of minimal fill-in for arbitrary graphs is given. The method of solution involves the development of new techniques for solving the connected minimal set system problem and combining them with some new divide-and-conquer methods.< >