De laatste jaren is er een groeiende interesse in het bestuderen van grafentheoretische structuren die worden gebruikt voor het ontwerpen van efficiënte algoritmen in verschillende rekenmodellen, zoals dynamische, parallelle en gedistribueerde modellen.

In dit artikel richten we ons op afstandsstructuren. Dit zijn objecten die benaderde afstanden in een grafiek bewaren, maar deze benaderingsfactor inruilen tegen ruimte, zoektijd of het aantal hops op de benaderde kortste paden. We beschrijven hoe deze structuren gebruikt kunnen worden voor het sneller berekenen van kortste paden in dynamische en parallelle modellen. Tot slot bespreken we hun toepassing in gerelateerde problemen zoals grafiekclustering.

 

Het FOAM Seminar, georganiseerd door computerwetenschappers van het ILLC, brengt onderzoek over vragen van fundamentele aard in computerwetenschap en AI, in onderzoeksgebieden zoals algoritmen, optimalisatie, gegevensbeheer, planning, kennisrepresentatie en multiagent systemen. De lezingen moeten breed toegankelijk zijn en op het niveau van een plenaire lezing van een relevante conferentie (zoals IJCAI, AAAI, KR, ICAPS, AAMAS, EC, PODS, LICS, STOC, FOCS en SODA).

FOAM vindt meestal plaats op vrijdag om 15:00 uur. De lezingen duren ongeveer 45 minuten, gevolgd door een korte discussie. Na afloop ben je uitgenodigd om te blijven voor een praatje en een drankje. Iedereen is welkom!

Meer informatie vind je op de website van LAB42.