IMSc Webinar

Dynamizing Graph Classes and Output Sensitive Fault Tolerant Subgraph Problems

Niranka Banerjee

The Institute of Mathematical Sciences

To analyze an algorithm for a graph problem the general notion is to assume that a graph is static. However, for most real world applications graphs are constantly modified. These modifications can be in terms of edge/vertex insertions or deletions or both. Two different models that study and analyze graphs in this setting are dynamic algorithms and fault tolerant algorithms. The aim is to maintain some property of the ever changing graph faster or in smaller size than the corresponding static algorithm. We will look at several classical graph problems and give upper and lower bounds for them in both the dynamic and the fault tolerant model.

Specifically, in this thesis we look at the following problems,

1) Maintaining a chordal graph under edge insertions and deletions,
2) Maintaining the value of the arboricity of the graph under edge insertions and deletions,
3) Giving tight bounds on a fault tolerant subgraph for maximum matching,
4) Giving tight bounds on a fault tolerant subgraph for various cut problems.

Join at: meet.google.com/ujd-jcrh-nhq

Note: This is a synopsis talk.