کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431682 | 688613 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved approximation algorithm for maximum edge 2-coloring in simple graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An improved approximation algorithm for maximum edge 2-coloring in simple graphs An improved approximation algorithm for maximum edge 2-coloring in simple graphs](/preview/png/431682.png)
چکیده انگلیسی
We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of 468575. This improves on the previous best (trivial) ratio of 45.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 205–215
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 205–215
نویسندگان
Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang,