Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1997 Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V
8942

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V