Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope