Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
DOI10.1007/3-540-60084-1_71zbMATH Open1412.68170OpenAlexW1632932043MaRDI QIDQ4645175FDOQ4645175
Authors: Sotiris E. Nikoletseas, J. Reif, P. G. Spirakis, Moti Yung 
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
Recommendations
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamic random networks and their graph limits
- The exponential time complexity of computing the probability that a graph is connected
- Acquaintance time of random graphs near connectivity threshold
- Stochastic processes in random graphs
- Cover time in edge-uniform stochastically-evolving graphs
- Cover time in edge-uniform stochastically-evolving graphs
- Approximating the Stochastic Network by its M Shortest Paths
- scientific article; zbMATH DE number 1263228
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Cites Work
- Title not available (Why is that?)
- A data structure for dynamic trees
- A topological approach to dynamic graph connectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Title not available (Why is that?)
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fully Dynamic Algorithms for 2-Edge Connectivity
- Fully dynamic planarity testing with applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Expected parallel time and sequential space complexity of graph and digraph problems
- Linear expected-time algorithms for connectivity problems
Cited In (2)
This page was built for publication: Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645175)
