discretization order

Vertex ordering with optimal number of adjacent predecessors

  • Tangi Migot
  • Jérémy Omer
    • Categories Combinatorial Optimization Tags , , ,

    In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function.Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such … Read more

    Constraint Programming Approaches for the Discretizable Molecular Distance Geometry Problem

  • Merve Bodur
  • Moira MacNeil
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular … Read more

    Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems

  • Merve Bodur
  • Moira MacNeil
    • Categories Branch and Cut Algorithms, Integer Programming, Other Topics Tags , , , ,

    Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in K-dimensional space such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called … Read more