Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
This question might be better posed at CSTheory: cstheory.stackexchange.com . –  Joseph O'Rourke Apr 20 '11 at 16:18
Thanks for the suggestion, Joseph. This question has been answered on SE at cstheory.stackexchange.com/questions/6364/… –  bbejot May 12 '11 at 4:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.