An optimal EREW PRAM algorithm for minimum spanning tree verification
From MaRDI portal
Publication:290239
DOI10.1016/S0020-0190(97)00050-1zbMath1337.68285MaRDI QIDQ290239
Vijaya Ramachandran, Santanu Sinha, Valerie King, Chung Keung Poon
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Tight bounds for distributed minimum-weight spanning tree verification, Distributed verification of minimum spanning trees, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear verification for spanning trees
- A simpler minimum spanning tree verification algorithm
- Optimal parallel verification of minimum spanning trees in logarithmic time
- Applications of Path Compression on Balanced Trees
- An Efficient Parallel Biconnectivity Algorithm
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time