Francisco Javier Zaragoza Martínez

Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

  • Andreas Bärmann
  • Patrick Gemander
  • Maximilian Merkert
  • Ann-Kathrin Wiertz
  • Francisco Javier Zaragoza Martínez
    • Categories Dynamic Programming, Graphs and Matroids, Polyhedra Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more

    The Non-Stop Disjoint Trajectories Problem

  • Benno Hoch
  • Frauke Liers
  • Sarah Neumann
  • Francisco Javier Zaragoza Martínez
    • Categories Combinatorial Optimization, Network Optimization Tags , , , , ,

    Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the \NP-complete disjoint paths problem, trajectories must … Read more