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

摘要

The first efficient parallel algorithm for computing minimalelimination ordering (MEO) of an arbitrary graph is designed. Thealgorithm works in O(log3n) parallel timeand O(nm) processors on aconcurrent-read-concurrent-write parallel random-access machine (CRCWPRAM) for an n-vertex, m-edge graph and is optimal upto polylogarithmic factor with respect to the best sequential algorithmof D. Rose et. al. (SIAM J. Comput., vol.5, p.266-83, 1976). Asan application, the first efficient parallel solution to the problem ofminimal fill-in for arbitrary graphs is given. The method of solutioninvolves the development of new techniques for solving the connectedminimal set system problem and combining them with some newdivide-and-conquer methods