I'm trying to understand a specific part from an article of Agarwal and co.
It is about Distance Oracles but there is a specific explanation of How to convert from average-degree graph to maximum-degree bounded graph with linear complexity.
I can't understand it so I need a simple language explanation...
This is the link to the article: http://arxiv.org/pdf/1201.2703.pdf and the specific explanation is in section 5.
From the article: (I don't understand the reduction)
Let G = (V, E) be a connected graph with average degree ∆. Given G, we will first create a ∆-degree bounded graph G∆ = (V∆ , E∆ ). Then, we show how can be used on G∆ to return stretch-s paths on G.
The Reduction: For each node v ∈ V , create α v = ⌈deg(v)/∆⌉ nodes v1 , v2 , . . . , vαv in V∆ . For each edge e = (u, v) ∈ E, if deg(u) ≤ ∆ and deg(v) ≤ ∆, create an edge e = (u1 , v1 ) in E∆ . For each node v ∈ V , we arbitrarily distribute N (v) in G to the nodes corresponding to v in G∆ such that for i = 1, 2, . . . , (α v − 1), |N (v) ∩ N (vi )| = ∆ and |N (v) ∩ N (vαv )| = (deg(v) − (α v − 1) · ∆). Finally, for each pair vi , vi+1 , we create an edge in E∆ of weight 0.
In order to answer an approximate distance query for any pair of nodes u, v ∈ V , we use D to answer approximate distance queries between u1 , v1 ∈ V∆ in G∆ and let the length of the path returned by the data structure be δ′ . We output the distance δ′ as an approximate distance for the pair of nodes in G.