کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
423566 | 685256 | 2016 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring
ترجمه فارسی عنوان
الگوریتمهای مرزی و پارامتر ثابت برای رنگ آمیزی نامناسب وزن دار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 181-195
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 181-195