The (maximum receiver-centric) interference of a geometric graph (von (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^ 1 3 ); (2) no connected graph with vertex set V has interference o((log n)^ 1 4 ); and (3) the minimum spanning tree of @math has interference Theta(( n)^ 1 2 ).
This lower bound is matched by an upper-bound: The upper bound in twod-upper is obtained by selecting @math vertices to act as , connecting the hubs into any connected network and then having each of the remaining nodes connect to its nearest hub. This idea was extended to two and higher dimensions by Halld 'orsson and Tokuyama @cite_5 , by using a special type of @math -net as the set of hubs:
@cite_5
1977762076
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs (S(u) V ). For a queried pair of nodes (u, v), the length of a shortest (u !- !v )-path passing through a hub node from (S(u) S(v) ) is then used as an upper bound on the distance between u and v.