4
$\begingroup$

What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"?

Edit: I am working on all-pair reachability problem in DAG and I strongly feel that I can achieve O(mn) time for the problem stated above by extending my approach. I have searched the internet enough to find the current best algorithm for this problem but all I can find is the solution to this problem: "For any pair of vertices in a given graph G, return one LCA for the same". And this problem is trivial and easy. And you don't need to google it for me! And read the problem correctly, it has more content than simply "lca" and "dag"! So, can someone please tell me now about the current best algorithm for the problem stated.

$\endgroup$
  • $\begingroup$ To summarise: Bender et al. cs.stonybrook.edu/~bender/pub/JALG05-daglca.pdf show how to find one LCA, in time $\tilde{O}(n^{2.688})$. In contrast, you want to generate the set of all LCAs, and are wondering whether an algorithm is known to do this in $o(mn)$ time. Is this correct? $\endgroup$ – András Salamon Jun 27 '13 at 13:16
  • $\begingroup$ @AndrásSalamon Indeed! $\endgroup$ – rkjha Jun 27 '13 at 16:10
  • 1
    $\begingroup$ @rkjha maybe you can clarify this in the question and remove the discussion in the edit ? $\endgroup$ – Suresh Venkat Jun 27 '13 at 17:22

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.