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.