Optimal parallel verification of minimum spanning trees in logarithmic time
From MaRDI portal
Publication:2365173
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
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