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

摘要

The Generalized Discretizable Molecular Distance Geometry Problem is adistance geometry problems that can be solved by a combinatorial algorithmcalled ``Branch-and-Prune''. It was observed empirically that the number ofsolutions of YES instances is always a power of two. We give a proof that thisevent happens with probability one.