A new algorithm for the minimum spanning tree verification problem

DOI10.1007/S10589-014-9702-8MaRDI QIDQ2340495zbMATH OpenOpenAlexFDO

Authors Matthew Williamson, K. Subramani

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

certificationdepth-first searchgraph theoryminimum spanning treeverification

Mathematics Subject Classification ID

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

Recommendations

• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• scientific article; zbMATH DE number 1670813
• An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
• A simpler minimum spanning tree verification algorithm
• A simpler minimum spanning tree verification algorithm

Cites work

• 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 randomized linear-time algorithm to find minimum spanning trees
• A simpler minimum spanning tree verification algorithm
• An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
• An inverse-Ackermann type lower bound for online minimum spanning tree verification
• Applications of Path Compression on Balanced Trees
• Distributed verification of minimum spanning trees
• Efficiency of a Good But Not Linear Set Union Algorithm
• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• Introduction to algorithms.
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

Cited in

(7)

• Minimum spanning tree verification under uncertainty
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• scientific article; zbMATH DE number 1264417 (Why is no real title available?)
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
• An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
• An inverse-Ackermann type lower bound for online minimum spanning tree verification

Describes a project that uses

Uses Software

• DIMACS
• Algorithm 447

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340495)