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. We start with the notion of partitioning a triangulated graph into a set of (mutually disjoint) adjacency-level sets and we present a parallel algorithm, based mainly on the properties of the adjacency-level sets, which computes a p.e.s. in time O(log L • log H) using L • H • n2 processors on a CRCW-PRAM. The computation of the adjacency-level sets of a triangulated graph can be done in time O(log L) with L • H • n2 processors within the same type of computational model. Here, L < n and H < n are the length and the height of the graph, respectively.