paper_8513

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(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.
Last Change: 12/01/08 at 16:58:18 Deutsch	University of Bonn -> Department of Computer Science -> Chair V