Alladi Ramakrishnan Hall

Dynamic Graph Matching

Manoj Gupta

Xerox Research, India

The aim of a dynamic graph problem is to maintain a property P of a graph
after each insertion or/and deletion of an edge. There has been a huge
amount of research in the area of dynamic graph problems like reachability,
shortest path, all pair shortest path etc.
However, dynamic graph matching received very less attention even though
there is a rich history for matching in static graphs.
However, the results for dynamic graph matching have started building up in
the last few years. In this talk, we will survey the history of the dynamic
graph matching problem and list our contribution in this history.