Dynamic Matching with Guarantees

Topic Description

In this thesis we want to develop a matching algorithm for dynamic graphs, i.e. edges can be inserted and deleted over time. The algorithm will have a performance guarantee such that if the update step takes 1/epsilon time the algorithm computes a 1+epsilon approximation to the matching problem.

You should have:

  • solid knowledge in algorithms and data structures
  • good knowledge in C++ and OpenMP