Microsoft Research Audio 103929: Dynamic Algebraic Algorithms

The algebraic methods had turned out to be very useful in many graph applications, starting from transitive closure computations and ending on counting perfect matchings. The constructed algorithms use matrix operations such as multiplication or computing determinant as a basic building block. Through this the algorithms usually gain on clearness. Also in many cases the algebraic approach yields the asymptotically fastest solutions. The basic example is the transitive closure problem.

The main topic of my talk is the application of the algebraic methods to a wider spectra of problems. I will show that also in dynamic setup the algebraic approach is very useful, for example to solve the dynamic transitive closure problem, the dynamic vertex connectivity problem and the dynamic maximum matching problem. Astonishingly, the ideas and techniques developed for the dynamic algorithms can also be used in static case in order to devise faster algorithms for the single source shortest path problem in graphs with integer edge weights as well as the maximum matching problems.