Problem najbliższego wspólnego przodka w grafach acyklicznych

Najbliższym wspólnym przodkiem dwóch wierzchołków u,v grafu acyklicznego jest wierzchołek będący wspólnym przodkiem wierzchołków u, v i nie będęcy przodkiem żadnego innego wspólnego przodka tych wierzchołków. Wybór najbliższego wspólnego przodka nie musi być jednoznaczny. W problemie najbliższego przodka w grafie acyklicznym pragniemy możliwie szybko odpowiadać na pytanie, który z wierzchołków grafu jest najbliższym wspólnym przodkiem dwóch dowolnie wybranych wierzchołków tego grafu. W tym celu stosujemy preprocessing umożliwiający odpowiedź na to pytanie w czasie stałym. Dotychczas najlepszy algorytm wykonywał preprocessing w czasie O(n^{(\omega+3)/2}, gdzie \omega=2,376. Z Andrzejem Lingasem poprawiliśmy nieco ten wynik do O(n^{2+(1/(4-\omega))}.