Spelling suggestions: "subject:"connectivity"" "subject:"biconnectivity""
1 |
Minimizing the maximum Interference in k-connected wireless networksMehrpour, Sahar 21 September 2016 (has links)
Given a set P of n points in R^d, we consider the k-connected interference minimization problem, in which the objective is to assign a transmission radius to each node in P such that the resulting network is k-connected and the maximum interference is minimized. We show for any n and any 1 <= k < n, Omega(sqrt(kn)) and Omega(k log n) are lower bounds on the worst-case minimum maximum interference in the symmetric and asymmetric models, respectively. In the symmetric case, we present polynomial-time algorithms that build a k-connected network on any given set of n nodes with interference O(sqrt(kn)) in one dimension and O(min{k sqrt(n), k log lambda}) in two dimensions, where lambda denotes the ratio of the longest to shortest distances between any pair of nodes. In the asymmetric case, we present a polynomial-time algorithm that builds a strongly k-connected network with maximum interference O(k log lambda) in two dimensions. / October 2016
|
Page generated in 0.0613 seconds