کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334270 | 690355 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
(p,k)-coloring problems in line graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The (p,k)-coloring problems generalize the usual coloring problem by replacing stable sets by cliques and stable sets. Complexities of some variations of (p,k)-coloring problems (split-coloring and cocoloring) are studied in line graphs; polynomial algorithms or proofs of NP-completeness are given according to the complexity status. We show that the most general (p,k)-coloring problems are more difficult than the cocoloring and the split-coloring problems while there is no such relation between the last two problems. We also give complexity results for the problem of finding a maximum (p,k)-colorable subgraph in line graphs. Finally, upper bounds on the optimal values are derived in general graphs by sequential algorithms based on Welsh-Powell and Matula orderings.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 462-474
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 462-474
نویسندگان
Marc Demange, Tınaz Ekim, Dominique de Werra,