Room 327

Dynamic Graph Algorithms

Keerti Choudhary

IIT Kanpur

There are many applications in real life which deal with graphs that are
dynamic in nature. Dynamic graph algorithm deals with obtaining efficient
solutions to a problem when the graph is constantly changing. The aim is to
maintain some data structure such that, it takes much less time to update
the solution than the best static algorithm whenever an edge/vertex is
added or deleted in the graph. In some situations, edges/vertices may only
be added (the incremental setting), while in other cases, edges/vertices
may only be deleted (the decremental setting). In the last twenty years,
many efficient dynamic algorithms have been designed for various
fundamental problems, namely, connectivity, reachability, shortest path,
transitive closure, etc. In this talk we will overview some of these
dynamic graph problems and important tools which have been used.