96-21
Isomorphism for Digraphs and Sequences of Shop Scheduling Problems
by Bräsel, H.; Harborth, M.; Willenius, P.
Preprint series: 96-21, Preprints
The paper is published: J. Combin. Math. Combinat. Comput. (to appear)
Abstract: The computational complexity of the graph isomorphism problem is stillunknown. We consider Cartesian products K n \Theta Km of two complete graphsK n and Km . An acyclic orientation of such a Cartesian product is called asequence graph because it has an application in production scheduling. It canbe shown that the graph isomorphism problem on the class of these acyclicdigraphs is solvable in polynomial time. We give numbers of non-isomorphicsequence graphs for small n and m. The orientation on the cliques of a sequencegraph can be interpreted as job orders and machine orders of a shop schedulingproblem with a complete operation set.
Keywords: complexity; graph isomorphism problem; acyclic digraphs; Latin rectangles; sequences; open shop scheduling
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.