Dynamiczne algorytmy dla silnie spójnych składowych i domknięcia przechodniego

Prelegent(ci)

Jakub Łącki

Afiliacja

Uniwersytet Warszawski

Termin

21 października 2010 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Zaprezentuję strukturę danych, która utrzymuje strukturę silnie spójnych składowych grafu skierowanego i obsługuje operacje usunięć krawędzi. Przy jej użyciu pokażę algorytm utrzymywania domknięcia przechodniego podczas usuwania krawędzi z grafu. Działa on deterministycznie i jest równie wydajny, jak najszybszy dotychczas znany algorytm randomizowany oraz o rząd wielkości szybszy od najszybszych algorytmów deterministycznych. Wszystkie prezentowane algorytmy są proste i opierają się jedynie na elementarnej wiedzy z teorii grafów.

---