Speaker: |
Rajesh Chitnis (Weizmann Institute of Science Faculty of Mathematics and Computer Science 234 Herzl St., Rehovot 7610001 Israel) |

Organiser: |
Kavitha Telikepalli |

Date: |
Tuesday, 10 Jan 2017, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In the first part of the talk, I will give a brief overview of FPT algorithms. This active area of research has seen many new developments over the last few years. The standard techniques for designing FPT algorithms on undirected graphs such as bidimensionality, treewidth-based dynamic programming, etc. seem to break down for directed graphs. I will present some of my work which overcomes this barrier, and designs optimal FPT and XP algorithms for cut and connectivity problems on directed graphs.

The second part of the talk will be about some recent work on parameterized streaming algorithms. For the Maximum Matching problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.