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

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

Given an undirected network with traversal times on its edges and connection requests from sources to destinations for commodities with 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 satisfy a non-stop … Read more