Jérémy Omer

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

    A polynomial algorithm for minimizing travel time in time-dependent networks with waits

  • Jérémy Omer
  • Michael Poss
    • Categories Network Optimization

    We consider a time-dependent shortest path problem with possible waiting at each node and a global bound $W$ on the total waiting time. The goal is to minimize only the time travelled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when … Read more