Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V
8513

01.12.2008

Fast Parallel Computation of Perfect and Strongly Perfect Elimination Schemes
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF]

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(log2n) parallel time and O(n4) 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 (log4n) time and O(n4) processors.

Last Change: 12/01/08 at 16:58:18
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V