Maintaining dynamic minimum spanning trees: an experimental study

DOI10.1016/J.DAM.2009.10.005zbMATH Open1225.05080DBLPjournals/dam/CattaneoFPI10OpenAlexW1990020944WikidataQ61609483 ScholiaQ61609483MaRDI QIDQ968158FDOQ968158

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1926664
• scientific article; zbMATH DE number 871915
• Maintaining minimum spanning trees in dynamic graphs
• Maintaining minimum spanning forests in dynamic graphs
• Algorithmic aspects in speech recognition

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 1926664 (Why is no real title available?)
• Dynamic maintenance of a shortest-path tree on homogeneous batches of updates: new algorithms and experiments
• Maintenance of a Spanning Tree For Dynamic Graphs by Mobile Agents and Local Computations
• Maintaining Nets and Net Trees under Incremental Motion
• scientific article; zbMATH DE number 1956218 (Why is no real title available?)
• A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

Describes a project that uses

Uses Software

• LEDA

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

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