Traffic Congestion in Expanders, $(p,δ)$--Hyperbolic Spaces and Product of Trees

In this paper we define the notion of $(p,δ)$--Gromov hyperbolic space where we relax Gromov's {\it slimness} condition to allow that not all but a positive fraction of all triangles are $δ$--slim. Furthermore, we study maximum vertex congestion under geodesic routing and show that it scales as $Ω(p^2n^2/D_n^2)$ where $D_n$ is the diameter of the graph. We also construct a constant degree family of expanders with congestion $Θ(n^2)$ in contrast with random regular graphs that have congestion $O(n\log^{3}(n))$. Finally, we study traffic congestion on graphs defined as product of trees.

No reviews yet.

No comments yet.