کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476388 | 699463 | 2006 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact method for graph coloring
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An exact method for graph coloring An exact method for graph coloring](/preview/png/476388.png)
چکیده انگلیسی
We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 33, Issue 8, August 2006, Pages 2189–2207
Journal: Computers & Operations Research - Volume 33, Issue 8, August 2006, Pages 2189–2207
نویسندگان
C. Lucet, F. Mendes, A. Moukrim,