کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420679 683968 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity results for minimum sum edge coloring
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Complexity results for minimum sum edge coloring
چکیده انگلیسی

In the Minimum Sum Edge Coloring problem we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. We show that the problem is (a) NP-hard for planar bipartite graphs with maximum degree 3, (b) NP-hard for 3-regular planar graphs, (c) NP-hard for partial 2-trees, and (d) APX-hard for bipartite graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 5, 6 March 2009, Pages 1034–1045
نویسندگان
,