Dynamic Graph Algorithms




Approximate Distance Oracles

Graph Blocking for External Searching

Graph Blocking corresponds to storing of a graph in external memory so that the number of I-O operations i.e. block transfers required to perform any arbitrary online walk can be minimized. We have provided an efficient solution for the case of planar graphs.

Efficient Dynamic Graph Algorithms


Graphs are used to model a lot of problems in various application areas of computer science. A few of such graph problems are : computing shortest path distance between a pair of nodes, computing minimum cost spanning tree etc. An efficient graph algorithm tries to solve a given graph problem in minimum time. In a large number of problems, the graph under consideration is not static. Instead it is changing. In a typical dynamic graph problem, initially a graph is given, followed by an online sequence of updates interspersed with queries. We have to carry out the updates and answer the queries online in an efficient manner. Each query has to be answered with respect to the graph present at that time, i.e. the answer to a query depends on upon all the updates preceding it. One trivial solution for solving such a dynamic graph problem is that we run the static graph algorithm after every update. Such solution is not acceptable since usually the efficient static graph algorithm takes too much time and the nature of application may not permit so much time.

The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time.

For every static graph problem there is a corresponding version of dynamic graph problem. The application areas of dynamic graph algorithms are communication network, graphics, assembly line, and VLSI design etc. For example, consider a computer network modeled by a graph where a node is mapped to a vertex and the link between two nodes is mapped to an edge. In real life networks, there is certain probability of a link to be down at a time. Consider the problem of maintaining connectivity information between every two nodes. Thus updates are of the form : add/remove link(u,v) and query can be : Is there a path from u to v? Similar problem can be of maintaining a minimum cost spanning tree in a dynamic environment where edge weights are changing.

We can classify dynamic graph problems according to the types of updates allowed. A problem is said to be fully dynamic if the update operations include unrestricted insertions and deletions of edges. A problem is called partially dynamic if only one type of update, either insertion or deletions, is allowed. If only insertions are allowed, the problem is called incremental; if only deletions are allowed, it is called decremental.