کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874788 | 688036 | 2014 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on maximum differential coloring of planar graphs
ترجمه فارسی عنوان
یک یادداشت در مورد حداکثر رنگ دیفرانسیل از نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the maximum differential coloring problem, where the vertices of an n-vertex graph must be labeled with distinct numbers ranging from 1 to n, so that the minimum absolute difference between two labels of any two adjacent vertices is maximized. As the problem is NP-hard for general graphs [16], we consider planar graphs and subclasses thereof. We prove that the maximum differential coloring problem remains NP-hard, even for planar graphs. We also present tight bounds for regular caterpillars and spider graphs. Using these new bounds, we prove that the Miller-Pritikin labeling scheme [19] for forests is optimal for regular caterpillars and for spider graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 29, November 2014, Pages 1-7
Journal: Journal of Discrete Algorithms - Volume 29, November 2014, Pages 1-7
نویسندگان
M.A. Bekos, M. Kaufmann, S. Kobourov, S. Veeramoni,