Dynamic Breadth First Search with Predictions

Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya

Given a graph $G(V,E)$ having $n$ vertices and $m$ edges, we maintain its Breadth-First Search (BFS) tree from source $s$ under an online sequence of edge updates in the prediction…