کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649361 1342450 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A polynomial algorithm for recognizing the AmAm-order class
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 12, 28 June 2009, Pages 4200–4204
نویسندگان
, ,