ON THE DISCRETIZATION OF DISTANCE GEOMETRY PROBLEMS
Antonio Mucherino, Carlile Lavor, Leo Liberti, Nelson Maculan · 2012
Distance geometry consists of finding an embedding of a weighted undirected graph in R n. Since some years, we are working on suitable discretizations forthis problem. Because of the discretization, the search domain is reduced froma 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.