On Efficient Distributed Construction of Near Optimal Routing Schemes

Michael Elkin, Ofer Neiman

Given a distributed network represented by a weighted undirected graph $G=(V,E)$ on $n$ vertices, and a parameter $k$, we devise a distributed algorithm that computes a routing sch…