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

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