LAB42 Talk | FOAM: Yasamin Nazari (VU) - Distance Structures and their Algorithmic Applications

LAB42, L3.33

Join us in this FOAM seminar from Yasamin Nazari from the VU.

Distance Structures and their Algorithmic Applications

In recent years there has been a growing interest in studying graph theoretical structures used for designing efficient algorithms in various computational models, such as dynamic, parallel and distributed models.

In this talk, we focus on distance structures which are objects that preserve approximate distances in a graph, but tradeoff this approximation factor with space, query time, or the number of hops on the approximate shortest paths. We describe how these structures can be utilized for faster shortest path computation in dynamic and parallel models. Finally, we discuss their application in related problems such as graph clustering.

FOAM seminars

The FOAM Seminar, organised by computer scientists at the ILLC, features research on questions of a fundamental nature in computer science and AI, in research areas such as algorithms, optimisation, data management, planning, knowledge representation, and multiagent systems. Talks are intended to be broadly accessible and pitched at the level you might find at a plenary talk of a relevant conference (such as IJCAI, AAAI, KR, ICAPS, AAMAS, EC, PODS, LICS, STOC, FOCS, and SODA).

FOAM usually takes place on a Friday at 15:00. Talks are roughly 45 minutes long, followed by a brief discussion. Afterwards, you are invited to stay for a chat and a drink. Everyone is welcome to attend!