An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM

DOI10.1006/JCSS.1996.0078zbMATH Open0870.68113OpenAlexW1978624651MaRDI QIDQ676443FDOQ676443

Authors: Shay Halperin, Uri Zwick 

Publication date: 7 September 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ff84ced32a0d569ee6d9d0a91c690d633885c164

Recommendations

• scientific article; zbMATH DE number 437524
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Fast Connected Components Algorithms for the EREW PRAM
• scientific article; zbMATH DE number 871942
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM

zbMATH Keywords

randomised EREW PRAM algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cited In (6)

• Constructing Light Spanners Deterministically in Near-Linear Time
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Many Random Walks Are Faster Than One
• Title not available (Why is that?)
• Optimal randomized EREW PRAM algorithms for finding spanning forests
• Constructing light spanners deterministically in near-linear time

This page was built for publication: An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676443)