|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 1997 | Copyright 1997 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |