Finding all k-cliques in k-partite graphs, an application in textile engineering

In many practical cases one has to choose an arrangement of different objec ts so that they are compatible. Whenever the compatibility of the objects c an be checked by a pair-wise comparison the problem can be modelled using t he graph-theoretic notion of cliques. We consider a special case of the pro blem where the objects can be grouped so that exactly one object in every g roup has to be chosen. This object has to be compatible to every other obje ct selected from the other groups. The problem was motivated by a braiding application from textile technology. The task is to route a set of thread-s pools (bobbins) on a machine from their origins to their destinations so th at collisions are avoided. We present a new model and algorithm in order to solve this important practical problem.