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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.