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