کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418497 | 681674 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A simple branching scheme for vertex coloring problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 1–2, January 2012, Pages 192–196
Journal: Discrete Applied Mathematics - Volume 160, Issues 1–2, January 2012, Pages 192–196
نویسندگان
Stefano Gualandi, Federico Malucelli,