Algorithms maintain BFS trees under dynamic updates with worst-case times O(η_v + η_e) incremental, O(min{m, η*_v + η_e}) decremental and fully dynamic, using O(mn) preprocessing.
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Dynamic Breadth First Search with Predictions
Algorithms maintain BFS trees under dynamic updates with worst-case times O(η_v + η_e) incremental, O(min{m, η*_v + η_e}) decremental and fully dynamic, using O(mn) preprocessing.