Discretization Vertex Orders in Distance Geometry

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 two mathematical programming formulations of some of these ordering problems

By: Andrea Cassioli , Oktay Günlük , Carlile Lavor , Leo Liberti

Published in: Discrete Applied Mathematics, volume 197, (no ), pages 27-41; SI 10.1016/j.dam.2014.08.035 in 2015

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .