Double clustering conjecture for bounded-doubling graph families

Let F1\mathcal{F}_1 and F2\mathcal{F}_2 be two families of graphs with bounded doubling dimension, not necessarily with the same constants. For any two graphs \G1F1\G_1\in\mathcal{F}_1 and \G2F2\G_2\in\mathcal{F}_2 of size nn, construct the double clustering graph using the random-permutation construction: (u,v)(u,v) is an edge whenever, for every wu,vw\neq u,v, d1(u,w)<d1(u,v)d_1(u,w)<d_1(u,v) implies d2(π(u),π(w))d2(π(u),π(v))d_2(\pi(u),\pi(w))\geq d_2(\pi(u),\pi(v)). Bounded-doubling navigability conjecture. The resulting double clustering graph allows greedy routing in O(logn)O(\log n) expected steps. Questions such as connectivity, diameter, and edge length remain open in some or all cases, so the conjecture is unresolved.

Sources & referencesView supporting material

Primary source

Oskar Sandberg, “Double Clustering and Graph Navigability”, arXiv:0709.0511 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.