
University of Bonn > Department of Computer Science > Chair V  
CSReports 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 CRCWPRAM 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 CREWPRAM 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 