Dynamic Algebraic Algorithms

August 16, 2007
Piotr Sankowski | Universita di Roma "La Sapienza"

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.

Speaker Details

Piotr Sankowski received a M.Sc. degree in Computer Science in 2002 and a Ph.D. degree in Computer Science in 2005, both from the Warsaw University, Poland. Later he become an associate professor at the Warsaw University. From September 2006 he is a post-doc fellow in University of Rome “La Sapienza”, Italy. Moreover, he received a M.Sc. degree in Physics in 2003 from the Warsaw University and is perusing Ph.D. studies in Physics at Polish Academy of Sciences. He has received the ESA’04, FOCS’04, ESA’05 Best Student Paper Awards and is the winner of Witold Lipski prize for Young Researchers in Computer Science.