What is the complexity status for the Nearest Common Ancestor Problem on Trees in which the leaves are attached to the tree in DFS order ? i.e. Suppose one is visiting a tree T in DFS, and at any time one wants to answers NCA queries as NCA(x,y) for any already visited vertices (x,y).

This can be done in constant time $O(1)$ per NCA query and leaf insertion on RAM machines (Gabow, Tarjan '83, Gabow '90), my question is:

what is currently known concerning this problem on Pointer-Machines ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.