Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

DOI10.1137/0221070zbMath0760.68032OpenAlexW1978099551MaRDI QIDQ4027854

Brandon Dixon, Monika R. Henzinger, Robert Endre Tarjan

Publication date: 9 March 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221070

zbMATH Keywords

sensitivity analysisminimum spanning treeprogram checkingnetwork optimizationdivide and conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (26)

Trans-dichotomous algorithms for minimum spanning trees and shortest paths ⋮ Succinct indices for path minimum, with applications ⋮ Optimal parallel verification of minimum spanning trees in logarithmic time ⋮ An optimal EREW PRAM algorithm for minimum spanning tree verification ⋮ Proof labeling schemes ⋮ A simpler minimum spanning tree verification algorithm ⋮ Minimum spanning trees in networks with varying edge weights ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Auction algorithm sensitivity for multi-robot task allocation ⋮ Distributed verification of minimum spanning trees ⋮ The saga of minimum spanning trees ⋮ Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint ⋮ Improved filtering for weighted circuit constraints ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ The swap edges of a multiple-sources routing tree ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ Improved algorithms for replacement paths problems in restricted graphs ⋮ Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\) ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ A simpler minimum spanning tree verification algorithm ⋮ Stability of Networks in Stretchable Graphs ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ A new algorithm for the minimum spanning tree verification problem ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

This page was built for publication: Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time