01.12.2008

We design fast parallel algorithms for the construction of perfect and strongly perfect elimination schemes (orderings) for chordal and strongly chordal graphs. In the case of chordal graphs the algorithm works in O(log²n) parallel time and O(n⁴) processors on a CREW PRAM, an improvement over the recent algorithms of [NNS] and [DK]. The parallel algorithm for strongly perfect elimination schemes works in (log⁴n) time and O(n⁴) processors.