An optimal EREW PRAM algorithm for minimum spanning tree verification

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)

zbMATH Keywords

parallel algorithmsdesign of algorithmsoptimal algorithmEREW PRAMminimum spanning tree verification

Mathematics Subject Classification ID

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

Related Items (3)

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

This page was built for publication: An optimal EREW PRAM algorithm for minimum spanning tree verification