Skip to Main content Skip to Navigation
Conference papers

A Parallel BP Algorithm for the Discretizable Distance Geometry Problem

Abstract : We propose a parallel version of the Branch & Prune (BP) algorithm for the Discretizable Distance Geometry Problem (DDGP), which consists in a subclass of Distance Geometry Problems (DGPs) that can be discretized. The main idea is to split a DDGP instance in as many subinstances as the number of processors involved in the computation, and to invoke the sequential version of BP on each processor. Due to the flexibility of the discretizing orderings that can be defined on the vertex sets of graphs G representing DDGP instances, the subdivision of the original instance can be performed so that all solutions generated by locally solving the several subinstances are represented in a common coordinate system. This way, the communication phase of the parallel algorithm, where the local solutions are combined in order to generate the final set of solutions, is very efficient. We present some preliminary computational experiments and we study the behavior of the algorithm in relation to the number of considered processors. We also give some directions for transforming DDGP instances in parallelizable instances, and to modify them in order to improve the efficiency of the proposed parallel algorithm.
Document type :
Conference papers
Complete list of metadata
Contributor : Antonio Mucherino Connect in order to contact the contributor
Submitted on : Saturday, November 24, 2012 - 1:49:36 PM
Last modification on : Tuesday, October 19, 2021 - 11:58:55 PM


  • HAL Id : hal-00756947, version 1


Antonio Mucherino, Gramacho Warley, Carlile Lavor, Nelson Maculan. A Parallel BP Algorithm for the Discretizable Distance Geometry Problem. Workshop on Parallel Computing and Optimization (PCO12), 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS12), 2012, Shanghai, China. ⟨hal-00756947⟩



Record views