Problem najbliższego wspólnego przodka w grafach acyklicznych

Prelegent(ci)

Mirosław Kowaluk

Afiliacja

Uniwersytet Warszawski

Termin

13 października 2005 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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

---