Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
It addresses the open problem of fully dynamic BFS in directed graphs, which is important for applications like network analysis and graph algorithms.
This paper presents a framework for maintaining a breadth-first spanning tree and BFS ordering in directed graphs under both edge insertions and deletions, achieving fully dynamic updates. The framework also supports single-source shortest paths and reachability queries.
We study the problem of maintaining a breadth-first spanning tree and the induced BFS ordering in a directed graph under edge updates. While semi-dynamic algorithms are known, maintaining the spanning tree, level information, and numbering together in the fully dynamic setting is less developed. This preprint presents a framework for fully dynamic BFS in directed graphs together with supporting data structures for maintaining the BFS tree, single-source shortest paths, and single-source reachability under both insertions and deletions.