Discretization vertex orders in distance geometry

作者：Cassioli Andrea; Guenluek Oktay; Lavor Carlile; Liberti Leo^*

来源：Discrete Applied Mathematics, 2015, 197: 27-41.

DOI：10.1016/j.dam.2014.08.035

• Molecular conformation
• Protein
• DDGP
• DMDGP
• Re-order
• Branch-and-Prune

When a weighted graph is an instance of the Distance Geometry Problem (DGP), certain types of vertex orders (called discretization orders) allow the use of a very efficient, precise and robust discrete search algorithm (called Branch-and-Prune). Accordingly, finding such orders is critically important in order to solve DGPs in practice. We discuss three types of discretization orders, the complexity of determining their existence in a given graph, and the inclusion relations between the three order existence problems. We also give three mathematical programming formulations of some of these ordering problems.

• 出版日期2015-12-31