Maintaining Minimum Spanning Forests in Dynamic Graphs
From MaRDI portal
Publication:2784458
DOI10.1137/S0097539797327209zbMath0996.68129MaRDI QIDQ2784458
Valerie King, Monika R. Henzinger
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (11)
Upper and lower bounds for fully retroactive graph problems ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Unnamed Item ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Dynamic kernels for hitting sets and set packing ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks
This page was built for publication: Maintaining Minimum Spanning Forests in Dynamic Graphs
