Randomization for efficient dynamic graph algorithms (invited talk)

DOI10.1007/978-3-319-29221-2_1MaRDI QIDQ2795930zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Deterministic network models in operations research (90B10)

Recommendations

• scientific article; zbMATH DE number 1857640
• scientific article; zbMATH DE number 1263228
• scientific article; zbMATH DE number 1304350
• scientific article; zbMATH DE number 2102755
• An introduction to randomized algorithms

Cites work

• A fully dynamic algorithm for maintaining the transitive closure
• A new approach to dynamic all pairs shortest paths
• An On-Line Edge-Deletion Problem
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Decremental Dynamic Connectivity
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Fully dynamic maximal matching in O( n) update time
• Fully dynamic randomized algorithms for graph spanners
• Fully-dynamic min-cut
• scientific article; zbMATH DE number 5764857 (Why is no real title available?)
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Improved Dynamic Reachability Algorithms for Directed Graphs
• On Dynamic DFS Tree in Directed Graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Sparsification—a technique for speeding up dynamic graph algorithms
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths

Cited in

(5)

• Random iteration algorithm for graph-directed sets
• Fully dynamic randomized algorithms for graph spanners
• scientific article; zbMATH DE number 1857640 (Why is no real title available?)
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
• The influence of random number generators on graph partitioning algorithms

This page was built for publication: Randomization for efficient dynamic graph algorithms (invited talk)

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