Maintaining minimum spanning trees in dynamic graphs

DOI10.1007/3-540-63165-8_214zbMath1401.68249OpenAlexW2128744826MaRDI QIDQ4571989

Valerie King, Monika R. Henzinger

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_214

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ How to use spanning trees to navigate in graphs ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ The saga of minimum spanning trees ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Fast reoptimization for the minimum spanning tree problem ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Reoptimization of minimum and maximum traveling salesman's tours

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• A data structure for dynamic trees
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
• An On-Line Edge-Deletion Problem
• Separator based sparsification for dynamic planar graph algorithms