کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875648 | 1441978 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fixing improper colorings of graphs
ترجمه فارسی عنوان
اصلاح رنگ های نامناسب از نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رفع اعداد، تنظیمات پیچیدگی پارامتریک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We provide a 2nâ
nO(1) algorithm for the problem and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the fixing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 66-78
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 66-78
نویسندگان
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, PaweÅ RzÄ
żewski,