Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
From MaRDI portal
Publication:4645175
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)
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
Cites work
- scientific article; zbMATH DE number 432745 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 1256641 (Why is no real title available?)
- scientific article; zbMATH DE number 1263228 (Why is no real title available?)
- scientific article; zbMATH DE number 910887 (Why is no real title available?)
- 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
- Expander properties in random regular graphs with edge faults
- Expected parallel time and sequential space complexity of graph and digraph problems
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Fully Dynamic Algorithms for 2-Edge Connectivity
- Fully dynamic planarity testing with applications
- Linear expected-time algorithms for connectivity problems
- On Finding and Updating Spanning Trees and Shortest Paths
- Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
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)
