Tata Institute of Fundamental Research
Some Recent Advances in Dynamic Graph Algorithms
STCS Seminar
Speaker:
Sayan Bhattacharya (University of Warwick
Department of Computer Science
Coventry, CV47AL
United Kingdom)
Organiser:
Arkadev Chattopadhyay
Date:
Friday, 13 Apr 2018, 11:45 to 12:45
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Many real-world networks such as the ones arising out of facebook and twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge nsertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of some recent developments in dynamic graph algorithms, focussing primarily on dynamic algorithms for graph coloring and maximum matching.
| Speaker: | Sayan Bhattacharya (University of Warwick Department of Computer Science Coventry, CV47AL United Kingdom) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Friday, 13 Apr 2018, 11:45 to 12:45 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Many real-world networks such as the ones arising out of facebook and twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge nsertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of some recent developments in dynamic graph algorithms, focussing primarily on dynamic algorithms for graph coloring and maximum matching.