by Bräsel, H., Harborth, M., Willenius, P..
Series: 1996-21, Preprints
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)