On the complexity of algorithms with predictions for dynamic graph problems
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 7788448 (Why is no real title available?)
- scientific article; zbMATH DE number 7788596 (Why is no real title available?)
- A novel prediction setup for online speed-scaling
- Algorithms with Predictions
- All-Pairs Almost Shortest Paths
- An On-Line Edge-Deletion Problem
- Competitive Caching with Machine Learned Advice
- Connectivity oracles for failure prone graphs
- Distance oracles for vertex-labeled graphs
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Dynamic connectivity: connecting to networks and geometry
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamically switching vertices in planar graphs
- Faster Online Matrix-Vector Multiplication
- Fine-grained complexity lower bounds for families of dynamic graphs
- Fully dynamic (1+ e)-approximate matchings
- Fully dynamic maximal matching in O( n) update time (corrected version)
- Fully dynamic maximal matching in constant update time
- Higher lower bounds from the 3SUM conjecture
- Improved distance oracles and spanners for vertex-labeled graphs
- Learning-augmented weighted paging
- Matrix-vector multiplication in sub-quadratic time (some preprocessing required)
- Near-Optimal Bounds for Online Caching with Machine Learned Advice
- Networks cannot compute their diameter in sublinear time
- New data structures for subgraph connectivity
- On dynamic shortest paths problems
- On the hardness of partially dynamic graph problems and connections to diameter
- Online graph algorithms with predictions
- Popular conjectures imply strong lower bounds for dynamic problems
- The Power of Dynamic Distance Oracles
- The power of vertex sparsifiers in dynamic graph algorithms
- Tight cell probe bounds for succinct Boolean matrix-vector multiplication
- Towards polynomial lower bounds for dynamic problems
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Cited in
(3)
This page was built for publication: On the complexity of algorithms with predictions for dynamic graph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906367)
