Problems using LCA form arhive.

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
diac_paul
New poster
Posts: 10
Joined: Fri Nov 05, 2004 12:07 pm
Location: Iasi, Romania
Contact:

Problems using LCA form arhive.

Post by diac_paul » Mon Sep 11, 2006 9:31 am

Does anyone knows problemes in the arhive that use or can use LCA (Lowest common ancestor)? Or from other sites ...
Thanks


Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Thu Oct 19, 2006 11:49 am

can anybody explain me O(log n) LCA algo or give any link?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Oct 19, 2006 7:12 pm

For each vertex V and each X, compute and store the vertex (2^X) steps above the vertex V.

This can be done in O(N log N).

Think how to do it, and then how to use this information to find the LCA for a pair of vertices in O(log N) time.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Oct 19, 2006 9:17 pm

In Gusfield ("Algorithms on Strings, Trees, and Sequences"), ch.8, they describe a constant time LCA with linear preprocessing.

I tried reading it, but that just went (waaay) over my head. They map the tree to a complete binary tree in linear time in some funky way, that part I don't understand. Then finding LCA is easy (that part I kinda understand).

It is actually a good book, but is a bit hard for me to follow.

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Fri Oct 20, 2006 10:35 am

http://www14.in.tum.de/konferenzen/Jass ... kiefer.pdf

very interesting link :)
this algorithm finds LCA using minimizator

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat Oct 21, 2006 5:58 am

You should try what misof said, it's pretty intuitive and it should be at most 30 lines of code.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Oct 21, 2006 11:39 pm

There is also a very easy to code algorithm due to Tarjan, in which you find the lca of several pairs of vertices during a dfs of the tree (in O(V+Q+alfa(V+Q)), where V is the number of vertices, Q the number of queries and alfa is the very slow-growing inverse of the Ackermann function). You can find it in an exercise somewhere in Cormen's book.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Oct 26, 2006 8:21 pm

Actually, you can do the precalc in O(nlogn) time by converting into an +/-1 RMQ problem in linear time, and then do the queries in O(1).

Of course, you can also precalc in O(n) and queries in O(1), and that part isn't so bad using the big/small universe paradigm. The general RMQ->LCA is probably the hardest part, but the other parts are very easy to understand.

The paper is here:
http://www.cs.sunysb.edu/~bender/pub/lca.ps

Post Reply

Return to “Algorithms”