Randomization for Efficient Dynamic Graph Algorithms

DOI10.1007/978-3-319-29221-2_1zbMath1434.68670OpenAlexW2444180128MaRDI QIDQ2795930

Surender Baswana

Publication date: 23 March 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-319-29221-2_1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Fully-dynamic min-cut
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Fully dynamic randomized algorithms for graph spanners
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• An On-Line Edge-Deletion Problem
• Sparsification—a technique for speeding up dynamic graph algorithms
• Decremental Dynamic Connectivity
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed 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
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• A fully dynamic algorithm for maintaining the transitive closure

This page was built for publication: Randomization for Efficient Dynamic Graph Algorithms