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

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