SPEAKER: Virginia Vassilevska
TIME: Wednesday 12-1pm, November 8, 2006
PLACE: NSH 1507
TITLE: A dominance approach to weighted graph problems
ABSTRACT:
Fast matrix multiplication allows us to obtain faster algorithms for many
graph problems. A notable example is that of detecting a triangle in a
graph - the naiive algorithm runs in O(n^3), while cubing the adjacency
matrix gives an O(n^2.38) algorithm. Other problems that have benefitted
from fast matrix multiplication include graph perfect matching, unweighted
APSP, linear programming.
Most of these problems are unweighted, and it is unclear how to apply the
matrix multiplication techniques to their weighted counterparts. We show
how to use a different kind of matrix product, the dominance product, to
solve some weighted problems such as finding a maximum weighted triangle
in a graph, computing bits of the distance product and finding the
bottleneck distances between all pairs of vertices.