Approximate distance oracles for unweighted graphs in Õ (n2) time
Surender Baswana, Sandeep Sen · Symposium on Discrete Algorithms · 2004
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly in o(n2) space, and yet answers any approximate distance query in constant time. They named this data-structure approximate distance oracle because of this feature. Given an integer k