Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time

DOI10.7155/JGAA.00365MaRDI QIDQ3196316zbMATH OpenOpenAlexFDO

Authors Seth Pettie

Publication date 29 October 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00365

zbMATH Keywords

deterministic algorithmrandomized linear time MST algorithmsplit-findmin data structure

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Algorithms and Computation
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• The saga of minimum spanning trees
• An optimal minimum spanning tree algorithm

Cited in

(10)

• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
• Algorithms and Computation
• Auction algorithm sensitivity for multi-robot task allocation
• Directed shortest paths via approximate cost balancing
• On calculation of the stability radius for a minimum spanning tree
• Efficient online sensitivity analysis for the injective bottleneck path problem

This page was built for publication: Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time

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