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
| Identifer | oai:union.ndltd.org:MANITOBA/oai:mspace.lib.umanitoba.ca:1993/31845 |
| Date | 21 September 2016 |
| Creators | Mehrpour, Sahar |
| Contributors | Durocher, Stephane (Computer Science), Li, Ben (Computer Science) Arino, Julien (Mathematics) |
| Source Sets | University of Manitoba Canada |
| Detected Language | English |
Page generated in 0.5501 seconds