I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all undirected graphs and that no such algorithm exists for directed graphs. I'm wondering if such an algorithm exists for rooted directed trees.
2
-
$\begingroup$ This question might be better posed at CSTheory: cstheory.stackexchange.com . $\endgroup$– Joseph O'RourkeCommented Apr 20, 2011 at 16:18
-
1$\begingroup$ Thanks for the suggestion, Joseph. This question has been answered on SE at cstheory.stackexchange.com/questions/6364/… $\endgroup$– bbejotCommented May 12, 2011 at 4:11
Add a comment
|