ľ¹Ï¸£ÀûÓ°ÊÓ

LET OP: Als een kandidaat een lekenpraatje houdt, start de livestream een kwartier eerder

Netwerken vind je op veel verschillende plekken: ze dienen als model voor wegen, sociale contacten of het internet. Het analyseren van een netwerk is vaak uitdagend door de grootte van het netwerk. Computers helpen met rekenkracht en snelle algoritmes. Maar welke algoritmes zijn geschikt om welk type netwerk te analyseren?

Om dit te onderzoeken bestuderen we verschillende eigenschappen van netwerken en verschillende wiskundige problemen die uit de netwerkanalyse voortkomen. We abstraheren netwerken tot grafen, een veelgebruikt wiskundig model voor netwerken. Voor veel problemen is al aangetoond dat er op algemene grafen geen snelle algoritmes kunnen bestaan. Maar dit is een onvolledig beeld van het algoritmelandschap: bij een eenvoudige graaf kan het wél mogelijk zijn om een efficiënt algoritme te ontwerpen. Welke eigenschappen moet de graaf hebben zodat we snelle algoritmes kunnen vinden?

Een voorbeeld van een eigenschap die wij bekijken is dat de graaf een bepaald patroon niet bevat, een zogeheten verboden patroon. Dit geeft kennis over de structuur van de graaf die we in een algoritme kunnen gebruiken. Voor deze eigenschap geven we een uiteenzetting van het landschap van het ‘Diameter’-probleem en bestuderen we het landschap van het ‘Subset Vertex Cover’-probleem, een variant van het bekende ‘Vertex Cover’-probleem.

We bekijken ook het stromingsparadigma, waarbij de graaf aan ons gepresenteerd wordt in een stroom, en geheugengebruik een limiterende factor is in plaats van de oplossingstijd. Voor dit paradigma ontdekken we het landschap van ‘Diameter’ en van ‘Independent Set’ en analyseren we in detail welke vorm de informatie in de stroom moet hebben om de problemen met weinig geheugen op te kunnen lossen.