کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419590 | 683841 | 2010 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of two coloring problems in cubic planar bipartite mixed graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NPNP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 5, 6 March 2010, Pages 592–596
Journal: Discrete Applied Mathematics - Volume 158, Issue 5, 6 March 2010, Pages 592–596
نویسندگان
B. Ries,