On the Discretization of Distance Geometry Problems

Abstract : 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.
Type de document :
Communication dans un congrès
Mathematics of Distances and Applications 2012 (MDA12), 2012, Varna, Bulgaria. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00756945
Contributeur : Antonio Mucherino <>
Soumis le : samedi 24 novembre 2012 - 13:43:18
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Identifiants

  • HAL Id : hal-00756945, version 1

Citation

Antonio Mucherino, Carlile Lavor, Leo Liberti, Nelson Maculan. On the Discretization of Distance Geometry Problems. Mathematics of Distances and Applications 2012 (MDA12), 2012, Varna, Bulgaria. 2012. 〈hal-00756945〉

Partager

Métriques

Consultations de la notice

485