کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649361 | 1342450 | 2009 | 5 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 309, Issue 12, 28 June 2009, Pages 4200–4204