On the Number of Solutions of the Discretizable Molecular Distance Geometry Problem

摘要

The Discretizable Molecular Distance Geometry Problem is a subset of instances of the distance geometry problem that can be solved by a combinatorial algorithm called "Branch-and-Prune". It was observed empirically that the number of solutions of YES instances is always a power of two. We perform an extensive theoretical analysis of the number of solutions for these instances and we prove that this number is a power of two with probability one.