A Parallel Algorithm for Computing Minimum Spanning Trees
Oh la la
Your session has expired but don’t worry, your message
has been saved.Please log in and we’ll bring you back
to this page. You’ll just need to click “Send”.
Your evaluation is of great value to our authors and readers. Many thanks for your time.
When you're done, click "publish"
Only blue fields are mandatory.
Your mailing list is currently empty.
It will build up as you send messages
and links to your peers.
besides you has access to this list.
Enter the e-mail addresses of your recipients in the box below. Note: Peer Evaluation will NOT store these email addresses log in
Your message has been sent.
Full text for this article was not available? Send a request to the author(s)
: A Parallel Algorithm for Computing Minimum Spanning Trees
Abstract : We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V; E) of n = jV j vertices and m = jEj edges on an EREW PRAM in O(log 3=2 n) time using n+m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems. List of Symbols O() Capital Oh, slanted (math) O Capital Oh 0 zero l ell 1 one o() Lowercase oh, slanted (math) o lowercase oh ff greek alpha 1 Introduction This paper describes a new parallel algorithm for computing the minimum spanning tree (MST) of a graph in the EREW PRAM model of parallel computation, the weakest of the PRAM models. This algorithm is faster by a factor of q log jV ...
: Computer Science
Leave a comment
This contribution has not been reviewed yet. review?