## Seminar SS2022

# Dynamic Algorithms

### Contents

In many problems that you might know, the correct input is given in advance and you can calculate a solution for the problem. This can happen for example in a routing problem, where you try to find a shortest path on a map between two given points.Now imagine you have calculated an optimal route, and have already started travelling: At some point, maybe a street is blocked or there is some delay due to traffic congestions. What can you do now?

Of course you can use your algorithm and calculate a new route, starting at zero. But is there maybe also a possibility to use some of the results that you have already calculated at the first attempt of finding a route?

These kind of problems are the so called "dynamic problems", and in this seminar we will talk about exactly those (and of course about algorithms, that handle in this setting).

Further examples of those problems can be found easily in every-day life, but for example also on Wikipedia

### Date and Time

The seminar will be held on a weekly basis. We expect you to actively participate during the presentations, e.g. asking questions and activating your camera, if the seminar is held online (if the seminar is not held online, questions and feedback will also be expected of course).The date of the kickoff-meeting will be announced before the start of the summer semester. The regular date and time will be announced after the topics are distributed.

Note that participating in this seminar requires a registration on Supra!

### Material

## Dates and Topics

The presentations start on May 5th. We meet Thursdays every week at 12:30 in the seminar room of the i1 except for holidays.Date | Topic |
Student |
---|---|---|

May 5th |
Connectivity on undirected graphs | Beka |

May 12th |
Minimum weight spanning tree | Lea |

May 19th |
Cycle Detection + Topological Ordering | Vincent |

June 2nd |
Matching | Xiaolu + Haihua |

June 23rd |
Motif counting | Jakob + Maxim |

June 30th |
Diameter | Gerrit |

June 30th |
Reoptimzation of Steiner trees | Linus |

July 7th |
On the Approximability of TSP on Local Modifications of Optimally Solved Instance |
Lasse |

July 14th |
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time | Tianjun |