Obliczanie odległości w grafie przy użyciu mnożenia macierzy

Prelegent(ci)

Piotr Sankowski

Afiliacja

Uniwersytet Warszawski

Termin

27 października 2005 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Tematem seminarium jest obliczanie odległości w grafie z wykorzystaniem mnożenia macierzy. Rozpocznę od przedstawienia tegorocznych wyników pokazujących w jaki sposób bliczyć odległości z zadanego wierzchołka w grafie dla całkowitoliczbowych wag krawędzi w takim samym czasie jak mnożenie macierzy rozmiaru n na n. Wynik ten został jednoczesnie przedstawony w pracach ,,Answering distance queries in directed graphs using fast matrix multiplication'' Raphael Yuster i Uri Zwick (FOCS'05) oraz ,,Shortest Paths in Matrix Multiplication Time'' Piotr Sankowski (ESA'05). Druga część seminarium będzie poświęcona obliczaniu odległości między wszystkimi parami wierzchołków w grafie. Skoncentruję się na przestawieniu wyników zawartych w pracy ,,All Pairs Shortest Paths in weighted directed graphs'' Uri Zwick (FOCS'98).

---