Maintaining minimum spanning forests in dynamic graphs

DOI10.1137/S0097539797327209MaRDI QIDQ2784458zbMATH OpenFDO

Authors Valerie King, Monika R. Henzinger

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539797327209

zbMATH Keywords

data structuredynamic graphgraph algorithmminimum spanning tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Maintaining minimum spanning trees in dynamic graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Faster Fully-Dynamic Minimum Spanning Forest
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Fully-dynamic minimum spanning forest with improved worst-case update time

Cited in

(27)

• Constant-time dynamic weight approximation for minimum spanning forest
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Dynamic kernels for hitting sets and set packing
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
• scientific article; zbMATH DE number 1617242 (Why is no real title available?)
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Algorithmic techniques for maintaining shortest routes in dynamic networks
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Faster Fully-Dynamic Minimum Spanning Forest
• Maintaining Nets and Net Trees under Incremental Motion
• Maintenance of a minimum spanning forest in a dynamic plane graph
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 1775391 (Why is no real title available?)
• Maintaining minimum spanning trees in dynamic graphs
• Maintenance of a Spanning Tree For Dynamic Graphs by Mobile Agents and Local Computations
• scientific article; zbMATH DE number 1926664 (Why is no real title available?)
• Maintaining centdians in a fully dynamic forest with top trees
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
• Fully-dynamic minimum spanning forest with improved worst-case update time
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Fully dynamic arboricity maintenance
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Upper and lower bounds for fully retroactive graph problems
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Maintaining dynamic minimum spanning trees: an experimental study

This page was built for publication: Maintaining minimum spanning forests in dynamic graphs

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