On the Discretization of Distance Geometry Problems
Résumé
Distance geometry consists of finding an embedding of a weighted undirected graph in R^n. Since some years, we are working on suitable discretizations for this problem. Because of the discretization, the search domain is reduced from a continuous to a discrete set which has the structure of a tree. Based on this combinatorial structure, we developed an efficient branch-and-prune (BP) algorithm for the solution of distance geometry problems. In this paper, we focus on two important aspects of the discretization: the identification of suitable vertex discretizing orderings and the analysis of the symmetries that can be found in BP trees.