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

Done