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

Speaker(s)

Piotr Sankowski

Affiliation

Uniwersytet Warszawski

Date

May 11, 2006, 12:15 p.m.

Room

room 5580

Seminar

Seminar Algorithms

---

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

---