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

Speaker(s)

Piotr Sankowski

Affiliation

Uniwersytet Warszawski

Date

Oct. 27, 2005, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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

---