Szybsze dynamiczne skojarzenia i spójność wierzchołkowa

Prelegent(ci)

Piotr Sankowski

Afiliacja

Uniwersytet Warszawski

Termin

11 maja 2006 12:15

Pokój

p. 5580

Seminarium

Seminarium "Algorytmika"

---

W ramach seminarium opowiem o pierwszych dynamicznych podkwadratowych algorytmach na obliczanie: liczby wierzchołkowo rozłącznych s,t-ścieżek, rozmiaru maksymalnego skojarzenia w grafie i skierowanej k-spójności wierzchołkowej. Prezentowane algorytmy są randomizowane z jednostronnym błędem. Algorytmy dynamiczne dla problemu rozmiaru maksymalnego skojarzenia i liczby wierzchołkowo rozłącznych ścieżek obsługuje operację zmiany w grafie w czasie O(n^1.495). Natomiast algorytm dla dynamicznej k-spójności wierzchołkowej obsługuje zmiany w czasie O(n^1.575 + nk^2). Jako rezultat uboczny otrzymujemy także dynamiczny algorytm na obliczanie rzędu macierzy obsługujący zmiany w czasie O(n^1.495).

---