Name
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 G c not satisfying π, and an edge-recoloring cost matrix R = r i j c × c where r i j ¿ 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 G c 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.08.016 | Theoretical Computer Science |
Keywords | Field | DocType |
Edge-colored graphs,Properly edge-colored paths,Trails and cycles,Monochromatic paths,Edge-recoloring cost | Discrete mathematics,Graph,Colored,Monochromatic color,Combinatorics,Cost matrix,Mathematics | Journal |
Volume | Issue | ISSN |
602 | C | 0304-3975 |
Citations | PageRank | References |
1 | 0.36 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luerbio Faria | 1 | 133 | 20.98 |
| Laurent Gourvès | 2 | 241 | 30.97 |
| Carlos A. J. Martinhon | 3 | 36 | 4.61 |
| Jérôme Monnot | 4 | 512 | 55.74 |