Improving the efficiency of parallel minimum spanning tree algorithms

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2003-03, Vol.126 (1), p.33-54
Main Authors: Chong, Ka Wong, Han, Yijie, Igarashi, Yoshihide, Lam, Tak Wah
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Connected components
Exact sciences and technology
Graph algorithms
Graph theory
Mathematics
Minimum spanning trees
Parallel algorithms
PRAM
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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( n 2) operations on the EREW PRAM.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(02)00560-7