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

Speaker(s)

Jakub Łącki

Affiliation

Uniwersytet Warszawski

Date

Oct. 21, 2010, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---