Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Sayan Bhattacharya: Some Recent Advances in Dynamic Graph Algorithms

LFCS seminar: Sayan Bhattacharya: Some Recent Advances in Dynamic Graph Algorithms

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When May 29, 2018
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

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 optimisation problem when the input graph keeps changing via a sequence of updates (edge insertions/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 colouring and maximum matching.

Document Actions