Lineair algoritme voor Greedy Weighted Graph Matching en de link met het Stable Marriage probleem

Abstract

Een matching is een deelverzameling van de kanten in een graaf, waarbij elk punt aan maximaal een ander punt gematcht is. Tussen het probleem op een gewone graaf, Greedy Matching, en op een bipartite graaf, het Stable Marriage probleem, is een link gevonden in 2016. Voor Greedy Matching heeft Preis in 1999 een lineair halfapproximatie-algoritme ontworpen. Voor het Stable Marriage probleem is nog geen lineair algoritme gevonden. Door de link tussen de problemen is de vraag of dit ook mogelijk is. De scriptie gaat in op de link en voornamelijk op het algoritme van Preis.