Problem najbliższego wspólnego przodka w grafach acyklicznych

Speaker(s)

Mirosław Kowaluk

Affiliation

Uniwersytet Warszawski

Date

Oct. 13, 2005, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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))}.

---