Home | english  | Impressum | Sitemap | KIT

Dynamic Matching with Guarantees

Dynamic Matching with Guarantees
Forschungsthema:Matching Algorithms

Sebastian Schlag, Christian Schulz

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