Smoothed analysis of dynamic graph algorithms
From MaRDI portal
Cites work
- A new approach to dynamic all pairs shortest paths
- All-Pairs Almost Shortest Paths
- Average-case analysis of dynamic graph algorithms
- Don't rush into a union, take time to find your roots
- Faster dynamic matchings and vertex connectivity
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Fully dynamic four-vertex subgraph counting
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 1099195 (Why is no real title available?)
- scientific article; zbMATH DE number 7774285 (Why is no real title available?)
- Logarithmic Lower Bounds in the Cell-Probe Model
- Models of smoothing in dynamic networks
- New techniques for proving fine-grained average-case hardness
- New unconditional hardness results for dynamic and online problems
- On dynamic shortest paths problems
- On smoothed analysis in dense graphs and formulas
- Popular conjectures imply strong lower bounds for dynamic problems
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
- Smoothed analysis of algorithms
- Smoothed analysis of balancing networks
- Smoothed analysis of dynamic networks
- Smoothed Analysis on Connected Graphs
- Smoothed analysis with adaptive adversaries
- Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
- Super-logarithmic lower bounds for dynamic graph problems
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- The complexity of average-case dynamic subgraph counting
- Towards polynomial lower bounds for dynamic problems
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
This page was built for publication: Smoothed analysis of dynamic graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445632)