Abstract: Distance geometry consists of finding an embedding of a weighted undirected graph in Rn. Since some years, we are working on suitable discretizations for this 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.

Keywords: distance geometry, discretization, combinatorial optimization, discretizing orderings, symmetries.

ACMClassification Keywords: G.2.1 Combinatorics - Combinatorial algorithms; B.5.2 Design Aids -Optimization; J.3 Life andMedical Sciences - Biology and genetics;

MSC: 05C85, 90C27, 51K99.

Link:

ON THE DISCRETIZATION OF DISTANCE GEOMETRY PROBLEMS

Antonio Mucherino,Carlile Lavor,Leo Liberti,Nelson Maculan

http://www.foibg.com/ibs_isc/ibs-25/ibs-25-p16.pdf