Optimal parallel verification of minimum spanning trees in logarithmic time

DOI10.1007/BF02523235zbMath0864.68046OpenAlexW2175995877MaRDI QIDQ2365173

Brandon Dixon, Robert Endre Tarjan

Publication date: 22 January 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02523235

zbMATH Keywords

verificationsensitivity analysisminimum spanning treesoptimal parallel algorithms

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (7)

An optimal EREW PRAM algorithm for minimum spanning tree verification ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Distributed verification of minimum spanning trees ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\) ⋮ An improved algorithm for hierarchical clustering using strong components ⋮ Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• A randomized linear-time algorithm for finding minimum spanning trees
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

This page was built for publication: Optimal parallel verification of minimum spanning trees in logarithmic time