Publications
Dynamic Graph Algorithms
Motivation
Papers
Graph-Spanners
-
Title : A Simple Linear time Algorithm for Computing
(2k-1)-spanner of
O(n^{1+1/k})
size for weighted graphs.
postscript gzipped
Co-author : Prof. Sandeep Sen
Conference : 30th International Colloquium on Automata, Languages
and Programming (ICALP) , June 30 - July 4, 2003
Venue : Eindhoven, The Netherlands
Approximate Distance Oracles
-
Title : Approximate Distance Oracles for Unweighted Graphs in
O(n^2 log n) Time.
Abstract
Co-author : Prof. Sandeep Sen
Conference : 15th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) , January 11-13, 2004 (to appear)
Venue : New Orleans, LA, USA.
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
Motivation
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.