Branch-and-Prune Algorithm for the Sensor Network Localization Problem
M.C. De Cola, A. Mucherino, G. Felici, L. Liberti

The Sensor Networks Localization Problem (SNLP) consists in seeking on embedding in R^2 of a given weighted undirected graph where the vertices represent the sensors in a global coordinate system and the weight of each edge is the Euclidean distance between two sensors. The SNLP belongs to the class of the problems of Distance Geometry (DGP). In this paper we describe the combinatorial property necessary to discretize the search space, by defining the discretizable sensor networks localization problem. We also describe a new version of the Branch & Prune (BP) algorithm, previously drawn for Molecular DGPs, adapt for solving instances of the SNLP. BP is an exact and exhaustive combinatorial algorithm that examines all the valid embeddings of a given weighted graph G = (V,E,d), under the hypothesis of existence of a given order on V. Finally, we show some computational results on a set of randomly generated instances.