Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Improving Parallel Computation with Fast Integer Sorting
| |
|
Improving Parallel Computation with Fast Integer Sorting
Ka Wong Chong6  , Yijie Han7 , Yoshihide Igarashi8 and Tak Wah Lam9
| (6) |
Department of Computer Science, The University of Hong Kong, Hong Kong, China |
| (7) |
Electronic Data Systems, Inc., 750T ower Drive, CPS, Mail Stop 7121, Troy, MI 48098, USA |
| (8) |
Department of Computer Science, Gunma University, Kiryu 376-8515, Japan |
| (9) |
Department of Computer Science, The University of Hong Kong, Hong Kong, China |
Abstract
This paper presents results which improve the e.ciency of parallel algorithms for computing minimum spanning trees. These
results are obtained by mainly applying fast integer sorting. For an input graph with n vertices and m edges our EREW PRAM minimum spanning tree algorithm runs in O(log n) time with
operations. Our CRCW PRAM minimum spanning tree algorithm runs in O(log n) time with O(( m + n) log log n) operations. These complexities relate to the complexities of parallel integer sorting. We also show that for dense graphs
we can achieve O(log n) time with O( n
2) operations on the EREW PRAM.
Keywords Parallel algorithms - graph algorithms - minimum spanning tree - integer sorting - PRAM
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|