A polynomial algorithm for recognizing the -order class

Recently new classes of directed, acyclic graphs with n vertices, namely A m -orders where m 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 A m -order class is O ( n 9 ) , hence independent of m . However, recognizing if a graph is in A m -orders for all m might be done in O ( n 3 ) 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 m . When the task graph is an A m -order, the problem is polynomial on m processors. Hence it is interesting to recognize such task graphs in a polynomial, independent of m time, especially when the number of processors is large, for instance on a computation grid.