Het Greedy Vertex Cover algoritme, diepteonderzoek naar de verhouding tussen graafdichtheid en prestatie van het ‘GVC’ algoritme op ongerichte ongewogen grafen

Abstract

In dit bachelor eindwerkstuk onderzoeken we de verhouding tussen de graafdichtheid van instanties en de prestatie van het ‘Greedy Vertex Cover’ algoritme op deze instanties. Dit onderzoek is uitgevoerd als vervolgonderzoek op een verband dat we in de data van het onderzoek van Gomes et al. (2006) leken waar te nemen. We hebben hiervoor twee experimenten uitgevoerd waarbij het tweede experiment voortvloeide uit inzichten over de (beperkingen van de) instanties uit het eerste experiment. De resultaten van ons onderzoek gingen op het eerste gezicht in tegen de observatie in de data van Gomes et al. Wij vonden een negatieve trend in hun data, terwijl onze data een positieve trend liet zien. Een diepere analyse van de oorspronkelijke data van Gomes et al., samengenomen met voortschrijdend inzicht uit ons eigen onderzoek leidde tot de conclusie dat dit patroon veroorzaakt wordt door de (beperkingen van de) gebruikte instanties en niet door de graafdichtheid. Met dit onderzoek hebben we beter inzicht gekregen in de mechanismen die de prestatie van het ‘Greedy Vertex Cover’ algoritme beïnvloeden. Wanneer we specifiek kijken naar de invloed van de graafdichtheid van instanties op de prestatie van het algoritme, dan lijkt er op basis van onze meetdata een positief verband te bestaan waarbij een lagere graafdichtheid tot een betere prestatie leidt.