Title of article
Improving the efficiency of parallel minimum spanning tree algorithms Original Research Article
Author/Authors
Ka Wong Chong، نويسنده , , Yijie Han، نويسنده , , Yoshihide Igarashi، نويسنده , , Tak-Wah Lam، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2003
Pages
22
From page
33
To page
54
Abstract
This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n)log n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m+n) log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n2) operations on the EREW PRAM.
Keywords
PRAM , Connected components , Graph algorithms , Parallel algorithms , Minimum spanning trees
Journal title
Discrete Applied Mathematics
Serial Year
2003
Journal title
Discrete Applied Mathematics
Record number
885505
Link To Document