MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
This question might be better posed at CSTheory: . – Joseph O'Rourke Apr 20 '11 at 16:18
Thanks for the suggestion, Joseph. This question has been answered on SE at… – 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.