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

**Series:** 1996-21, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

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.

**Keywords:**

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

**This paper was published in:**

J. Combin. Math. Combinat. Comput. (to appear)