A new algorithm for the minimum spanning tree verification problem

DOI10.1007/s10589-014-9702-8zbMath1311.90167OpenAlexW2059619221MaRDI QIDQ2340495

Matthew Williamson, K. Subramani and Vahan Mkrtchyan

Publication date: 20 April 2015

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-014-9702-8

zbMATH Keywords

verificationgraph theoryminimum spanning treedepth-first searchcertification

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• DIMACS
• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• An inverse-Ackermann type lower bound for online minimum spanning tree verification
• A faster algorithm for the single source shortest path problem with few distinct positive lengths
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• A simpler minimum spanning tree verification algorithm
• Applications of Path Compression on Balanced Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Efficiency of a Good But Not Linear Set Union Algorithm
• A randomized linear-time algorithm to find minimum spanning trees
• Distributed verification of minimum spanning trees
• An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees

This page was built for publication: A new algorithm for the minimum spanning tree verification problem