A polynomial algorithm for recognizing the AmAm-order class

Recently new classes of directed, acyclic graphs with nn vertices, namely AmAm-orders where mm is a larger than 1 integer, have been presented. These classes contain the interval orders, but are incomparable to trees. Here it is shown that the complexity of recognizing the AmAm-order class is O(n9)O(n9), hence independent of mm. However, recognizing if a graph is in AmAm-orders for all mm might be done in O(n3)O(n3) time. These classes have an application in the preemptive multiprocessor scheduling problem. This problem is NP-hard if the number of processors is arbitrary but open for a fixed number of processors mm. When the task graph is an AmAm-order, the problem is polynomial on mm processors. Hence it is interesting to recognize such task graphs in a polynomial, independent of mm time, especially when the number of processors is large, for instance on a computation grid.