IMSc Webinar

Dynamizing Graph Classes and Output Sensitive Fault Tolerant Subgraph Problems

Niranka Banerjee

Research Institute of Mathematical Sciences, Kyoto University

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. In dynamic algorithms, the aim is to maintain some property of the ever
changing graph faster than the static algorithm. In fault tolerant model, the aim is to maintain a subgraph of small size that maintains the property under faults.

In this thesis, we look at several classical graph problems and give upper
and lower bounds for them in both the dynamic and the fault tolerant models.
Specifically, we look at the following problems,
1) Maintaining a chordal graph under edge deletions,
2) Maintaining the value of the arboricity of the graph under edge insertions and deletions,
3) Obtaining a small subgraph that maintains the size of a maximum matching of the given graph under faults.
4) Obtaining a small subgraph that maintains the size of a minimum (or s-t) cut in the given graph under faults.Venkatesh Raman is inviting you to a scheduled Zoom meeting.

Use the following Zoom link to join the meeting.

Join Zoom Meeting
zoom.us/j/5602350459?pwd=dC9TdkJxRXlVU0xxWmJPdkpGWlNGZz09

Meeting ID: 560 235 0459
Passcode: 127040