An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
Elias Dahlhaus, Marek Karpiński · 1989
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.>