Improving the efficiency of parallel minimum spanning tree algorithms

DOI10.1016/S0166-218X(02)00560-7zbMath1011.68176OpenAlexW1993446777WikidataQ58063040 ScholiaQ58063040MaRDI QIDQ1861567

Ka Wong Chong, Yoshihide Igarashi, Yijie Han, Tak-Wah Lam

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00560-7

zbMATH Keywords

parallel algorithmsgraph algorithmsPRAMminimum spanning treesconnectedcomponents

Mathematics Subject Classification ID

Trees (05C05) Parallel algorithms in computer science (68W10)

Related Items (3)

On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ An I/O Efficient Algorithm for Minimum Spanning Trees ⋮ On the Strongly Connected and Biconnected Components of the Complement of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• An optimally efficient selection algorithm
• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• An Efficient Parallel Biconnectivity Algorithm
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Parallel Merge Sort
• Computing connected components on parallel computers
• Efficient parallel algorithms for some graph problems
• A Parallel Algorithm for Computing Minimum Spanning Trees

This page was built for publication: Improving the efficiency of parallel minimum spanning tree algorithms