کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428750 686904 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of approximation of 3-edge-coloring of graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Complexity of approximation of 3-edge-coloring of graphs
چکیده انگلیسی

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. To make the gap more precise, we study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We show that it is an NP-hard problem to approximate such invariants with an error O(n1−ε), where n denotes the order of the graph and 0<ε<1 is a constant.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 4, 31 October 2008, Pages 238-241