A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

DOI10.7155/jgaa.00609OpenAlexW4313303087MaRDI QIDQ5886043

Paul Burkhardt, David A. Bader

Publication date: 30 March 2023

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

Full work available at URL: https://arxiv.org/abs/1908.03473

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Maintaining dynamic minimum spanning trees: an experimental study
• A linear-time algorithm for a special case of disjoint set union
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Algorithms for updating minimal spanning trees
• Efficient algorithms for finding the most vital edge of a minimum spanning tree
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A note on finding the bridges of a graph
• Applications of Path Compression on Balanced Trees
• Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
• An optimal minimum spanning tree algorithm
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• On Finding and Updating Spanning Trees and Shortest Paths
• Maintaining minimum spanning trees in dynamic graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Algorithms and Computation
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide

This page was built for publication: A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges