کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333910 | 689839 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem](/preview/png/10333910.png)
چکیده انگلیسی
In the paper, we show that the PDTC problem can be solved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when hâ¥6 is a fixed constant, but s is unbounded.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6261-6268
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6261-6268
نویسندگان
Flavia Bonomo, Sara Mattia, Gianpaolo Oriolo,