A simpler minimum spanning tree verification algorithm

DOI10.1007/BF02526037zbMath0868.68061OpenAlexW2089290774MaRDI QIDQ1355729

Valerie King

Publication date: 28 May 1997

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

spanning tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Succinct indices for path minimum, with applications ⋮ An optimal EREW PRAM algorithm for minimum spanning tree verification ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Streaming graph computations with a helpful advisor ⋮ Distributed verification of minimum spanning trees ⋮ The saga of minimum spanning trees ⋮ CASCADING RANDOM WALKS ⋮ A new algorithm for the minimum spanning tree verification problem ⋮ Optimal Algorithms for Geometric Centers and Depth

Cites Work

• Unnamed Item
• Linear verification for spanning trees
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• A randomized linear-time algorithm to find minimum spanning trees