Od macierzy odwrotnoścci do dynamicznych najkrótszych ścieżek

Speaker(s)

Piotr Sankowski

Affiliation

Uniwersytet Warszawski

Date

Oct. 28, 2004, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

W trakcie seminarium przedstawię najważniejsze elementy konstrukcji algorytmów dla dynamicznego liczenia macierzy odwrotnej oraz ich zastosowanie do liczenia dynamicznego domknięcia przechodniego. Konstrukcja ta daje asymptotyczne najszybsze znane algorytmy dla tego problemu. W drugiej części seminarium opowiem o rozszerzeniach przedstawionych metod dla obliczeń nad pierścieniami. Rozszerzenie to umożliwi konstrukcję efektywnych dynamicznych algorytmów na obliczanie długości najkrótszych ścieżek w grafie.

---