کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328508 | 684040 | 2005 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A hypocoloring model for batch scheduling
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Starting from a batch scheduling problem, we consider a weighted subcoloring in a graph G; each node v has a weight w(v); each color class S is a subset of nodes which generates a collection of node disjoint cliques. The weight w(S) is defined as max{w(K)=âvâKw(v)|KâS}. In the scheduling problem, the completion time is given by âi=1kw(Si) where S=(S1,â¦,Sk) is a partition of the node set of graph G into color classes as defined above. Properties of such colorings concerning special classes of graphs (line graphs of cacti, block graphs) are stated; complexity and approximability results are presented. The associated decision problem is shown to be NP-complete for bipartite graphs with maximum degree at most 39 and triangle-free planar graphs with maximum degree k for any k⩾3. Polynomial algorithms are given for graphs with maximum degree two and for the forests with maximum degree k. An (exponential) algorithm based on a simple separation principle is sketched for graphs without triangles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 3-26
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 3-26
نویسندگان
D. de Werra, M. Demange, J. Monnot, V.Th. Paschos,