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.

 

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!

 

You can find more information on the website of LAB42.