Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1997 Copyright 1997 University of Bonn, Department of Computer Science, Abt. V
85180

Ultrafast Randomized Parallel Construction- and Approximation Algorithms for Spanning Forests in Dense Graphs
Anders Dessmark, Carsten Dorgerloh, Andrzej Lingas, Juergen Wirtgen
[Download PostScript] [Download PDF]

We present a first randomized $\O$$(\log^{(k)} n)$ time and $\O$$(n + m)$ work CRCW-PRAM algorithm for finding a spanning forest of an undirected dense graph with $n$ vertices. Furthermore we construct a randomized $\O$$(\log \log n)$ time and $\O$$(n \log n)$ work CREW-PRAM algorithm for finding spanning trees in random graphs. Our algorithm is optimal with respect to time, work and space.

Last Change: 11/05/14 at 10:04:41
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V