Relay placement for two-connectivity

Motivated by applications to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a multiset of points in the two-dimensional plane. We must place a minimum-size (multi)set Q of wireless relay nodes in the two dimensional plane such that the unit-disk graph induced by the union of S and Q is two-connected. The unit-disk graph of a set of points has an edge between two points if their Euclidean distance is at most 1. In Infocom 2006, Kashyap, Khuller, and Shayman present two algorithms, both with approximation ratio of 10 for the two variants of the problem: two-edge-connectivity and biconnectivity. We use variants of the same algorithms, with improved analysis, to obtain approximation ratios of 9 for two-edge-connectivity, and 5 for biconnectivity respectively.

Event Topic

Discrete Applied Math Seminar