E. Dahlhaus et M. Karpinski, AN EFFICIENT PARALLEL ALGORITHM FOR THE MINIMAL ELIMINATION ORDERING (MEO) OF AN ARBITRARY GRAPH, Theoretical computer science, 134(2), 1994, pp. 493-528
Citations number
39
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
We design the first efficient parallel algorithm for computing the min
imal elimination ordering (MEO) of an arbitrary graph. The algorithm w
orks in O(log(3) n) parallel time and O(nm) processors on CREW PRAM, f
or an n-vertex, in-edge graph, and is optimal up to a polylogarithmic
factor with respect to the best sequential algorithm of Rose, et al. (
1976). The MEO problem for arbitrary graphs arises in a number of comb
inatorial optimization problems, as well as in database applications,
scheduling problems, and the sparse Gaussian elimination on symmetric
matrices. It was believed before to be inherently sequential, and stro
ngly resisting sublinear parallel time (sublinear sequential storage)
algorithms. As an application, this paper gives the first efficient pa
rallel solutions to the problem of minimal fill-in for arbitrary graph
s and connected combinatorial optimization problems (see e.g. Rose et
al., 1976; Tarjan, 1985), and to the problem of the Gaussian eliminati
on of sparse symmetric matrices (Rose, 1970; 1973) (The problem of com
puting a minimum fill-in is known to be NP-complete (Yannakakis, 1981)
. The method of solution involves a development of new techniques for
solving connected minimal set system problem, and combining it with so
me new divide-and-conquer methods.