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

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Bisseling, R. H.
dc.contributor.author	Veldhuis, T.
dc.date.accessioned	2017-02-22T18:20:49Z
dc.date.available	2017-02-22T18:20:49Z
dc.date.issued	2017
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/25464
dc.description.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.
dc.description.sponsorship	Utrecht University
dc.format.extent	407336
dc.format.mimetype	application/pdf
dc.language.iso	nl
dc.title	Lineair algoritme voor Greedy Weighted Graph Matching en de link met het Stable Marriage probleem
dc.type.content	Bachelor Thesis
dc.rights.accessrights	Open Access
dc.subject.courseuu	Wiskunde & Toepassingen