Generating edge-disjoint sets of quadruples in parallel for the molecular conformation problem

Tightening interatomic distance bounds, obtained from NMR experiments, is a critical step in solving the molecular conformation problem. Tetrangle inequality (resulting from the Cayley-Menger determinant for the 3-D embedding) is applied to quadruples of atoms in order to tighten the distance bounds. Complete graph Kn is used to model an n-atom molecule, where the nodes represent the atoms. Only edge-disjoint sets of quadruples can be processed in parallel. In this paper we propose a coarse-grain parallelization for generating edge-disjoint sets of quadruples in parallel. Previous methods for generating edge-disjoint quadruples relied on difference sets. Our approach partitions the nodes into disjoint sets (partitions). Quadruples are then generated based on their node distribution among these sets. 1