Zurück zu den Preprints des Jahres 1996


Isomorphism for Digraphs and Sequences of Shop Scheduling Problems

by Bräsel, H., Harborth, M., Willenius, P..

Series: 1996-21, Preprints

90B35 Scheduling theory, deterministic

The computational complexity of the graph isomorphism problem is still
unknown. We consider Cartesian products K n \Theta Km of two complete graphs
K n and Km . An acyclic orientation of such a Cartesian product is called a
sequence graph because it has an application in production scheduling. It can
be shown that the graph isomorphism problem on the class of these acyclic
digraphs is solvable in polynomial time. We give numbers of non-isomorphic
sequence graphs for small n and m. The orientation on the cliques of a sequence
graph can be interpreted as job orders and machine orders of a shop scheduling
problem with a complete operation set.

complexity; graph isomorphism problem; acyclic digraphs; Latin rectangles; sequences; open shop scheduling

This paper was published in:
J. Combin. Math. Combinat. Comput. (to appear)