Given a weighted directed graph with nonnegative edge weights and a vertex $r$ designated as root, at each step I will do one of the following:
- Add a new edge to the graph.
- Remove an edge from the graph.
After each step I need to find a minimum weight arborescence rooted at $r$. An arborescence is a spanning tree where all edges are directed away from the root (i.e. where the in-degree is $0$ for the root and $1$ for all other vertices).
I can do this by running Chu–Liu/Edmonds' algorithm every time an edge that is part of the current arborescence is deleted or a new edge is added. But I am looking for a more efficient way, as the number of steps can be large. Is there any existing algorithm suited for this? Could Chu–Liu/Edmonds' be extended for it?
