Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs

Perfect elimination schemes (p.e.s.) occur in a number of important problems such as perfect Gaussian elimination. The main objective of this paper is to study the parallel computation of p.e.s. of a triangulated or perfect elimination graph G=(V,E), with n=ℝVℝ vertices. The authors start with the notion of partitioning a triangulated graph into a set of (mutually disjoint) adjacency-level sets and they present a parallel algorithm, based mainly on the properties of the adjacency-level sets, which computes a p.e.s. in time O(logLëlogh) using LëHën² processors on a CRCW-PRAM. The computation of the adjacency-level sets of a triangulated graph can be done in time O(logL) with LëHën² processors within the same type of computational model. Here, L<n and H<n are the length and the height of the graph, respectively.