Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
From MaRDI portal
Publication:4645175
DOI10.1007/3-540-60084-1_71zbMath1412.68170OpenAlexW1632932043MaRDI QIDQ4645175
Mordechai M. Yung, John H. Reif, Paul G. Spirakis, Sotiris E. Nikoletseas
Publication date: 10 January 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60084-1_71
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A topological approach to dynamic graph connectivity
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Expected parallel time and sequential space complexity of graph and digraph problems
- A data structure for dynamic trees
- Fully dynamic planarity testing with applications
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Linear expected-time algorithms for connectivity problems
- Fully Dynamic Algorithms for 2-Edge Connectivity
- On Finding and Updating Spanning Trees and Shortest Paths
- Expander properties in random regular graphs with edge faults
- Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing