Article ID Journal Published Year Pages File Type
437612 Theoretical Computer Science 2015 14 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,