Discretization vertex orders in distance geometry
2015
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
41
Citations
NaN
KQI