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. Abstract The main purpose of this paper is to introduce the capacitated hub-and-spoke network design problem in which hubs have limited capacity for channelling flows between the nodes served by the system. The problem is formulated under a networking policy allowing both direct (nonstop) and hub connected (one-hub-stop and two-hub-stop) services between the nodes. A branch and bound algorithm and a heuristic procedure partitioning the set of solutions on the basis of hub locations are presented. In both algorithms, after identifying a set of hub locations, the problem is reduced into a smaller routing problem. Subgradient optimization is then applied to a Lagrangian relaxation of the reduced problem. The model and the proposed algorithms were applied to the air transportation system using data on passenger flows between the top forty US cities in 1989 (accounting for 73.32 of the surveyed passenger flow). Computational results from 141 problems suggest that both algorithms are effective at finding good solutions to this problem. We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [ Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356--361] showed an upper bound for R of dO(d) m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of @math , where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the first subexponential algorithm for this exploration problem, which achieves an upper bound of dO(log d) m. We also show a matching lower bound of @math for our algorithm. Additionally, we give lower bounds of @math , respectively, @math for various other natural exploration algorithms. We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k...