Double clustering conjecture for bounded-doubling graph families
Double clustering conjecture for bounded-doubling graph families
Let and be two families of graphs with bounded doubling dimension, not necessarily with the same constants. For any two graphs and of size , construct the double clustering graph using the random-permutation construction: is an edge whenever, for every , implies . Bounded-doubling navigability conjecture. The resulting double clustering graph allows greedy routing in 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.