
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 Universität Bonn, Institut für Informatik, Abt. V  
8533

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph
Elias Dahlhaus, Marek Karpinski [Download PostScript] [Download PDF] We design the first efficient parallel algorithm for computing the minimal elimination ordering (MEO) of an arbitrary graph. The algorithm works in $O(\log^3 n)$ parallel time and $O(nm)$ processors on a CREW PRAM, for an $n$vertex, $m$edge graph, and is optimal up to a polylogarithmic factor with respect to the best sequential algorithm of Rose, Tarjan and Lueker (\cite{RTL 76}). The MEO problem for ar\bi\trar\y graphs a\ri\ses in a num\ber of combinatorial 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 strongly resisting sublinear parallel time (sublinear sequential storage) algorithms. As an application, this paper gives the first efficient parallel solutions to the problem of {\em minimal fillin\/} for arbitrary graphs and connected combinatorial optimization problems (see \cite{RTL 76}, \cite{Ta 85}, for example), and to the problem of the Gaussian elimination of sparse symmetric matrices (\cite{Ro 70}, \cite{Ro 73}). (The problem of computing a {\em minimum fillIn\/} is known to be {\it NP}complete, \cite{Ya 81}.) The method of solution involves a development of new techniques for solving connected minimal set system problem, and combining it with some new divideandconquer methods. 

Last Change:
12/10/08 at 16:19:09
English 
Universität Bonn > Institut für Informatik > Abteilung V 