کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437612 690164 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
چکیده انگلیسی

We introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property π, a c  -edge-colored graph GcGc not satisfying π  , and an edge-recoloring cost matrix R=[rij]c×cR=[rij]c×c where rij≥0rij≥0 denotes the cost of changing color i of edge e to color j  . Basically, in this kind of problem the idea is to change the colors of one or more edges of GcGc in order to construct a new edge-colored graph such that the total edge-recoloring cost is minimized and property π is satisfied. We also consider the destruction of potentially undesirable structures with the minimum edge-recoloring cost. In this paper, we are especially concerned with the construction and destruction of properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs. Some related problems and future directions are presented.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 89–102
نویسندگان
, , , ,