Maintaining dynamic minimum spanning trees: an experimental study

DOI10.1016/j.dam.2009.10.005zbMath1225.05080OpenAlexW1990020944WikidataQ61609483 ScholiaQ61609483MaRDI QIDQ968158

B. E. Eshmatov

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.10.005

zbMATH Keywords

experimental analysisdynamic graphsminimum spanning tree algorithms

Mathematics Subject Classification ID

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

Related Items (1)

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

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Average-case analysis of dynamic graph algorithms
• A data structure for dynamic trees
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Randomized search trees
• Fully dynamic all pairs shortest paths with real edge weights
• Maintaining Minimum Spanning Forests in Dynamic Graphs
• Speeding Up Dynamic Shortest-Path Algorithms
• Maintaining information in fully dynamic trees with top trees
• Experimental analysis of dynamic all pairs shortest path algorithms
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Self-adjusting binary search trees
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Separator-Based Sparsification II: Edge and Vertex Connectivity
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Sparsification—a technique for speeding up dynamic graph algorithms
• Paths in graphs
• A new approach to dynamic all pairs shortest paths
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
• Algorithmic aspects in speech recognition
• Power balance and apportionment algorithms for the United States Congress
• An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
• A fully dynamic algorithm for maintaining the transitive closure

This page was built for publication: Maintaining dynamic minimum spanning trees: an experimental study