The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
Luerbio, Faria; Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme (2015), The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles, Theoretical Computer Science, 602, p. 89-102. 10.1016/j.tcs.2015.08.016
Type
Article accepté pour publication ou publiéDate
2015Journal name
Theoretical Computer ScienceVolume
602Publisher
Elsevier
Pages
89-102
Publication identifier
Metadata
Show full item recordAuthor(s)
Luerbio, FariaState University of Rio de Janeiro
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Martinhon, Carlos A.
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.Subjects / Keywords
Edge-colored graphs; Properly edge-colored paths; Trails and cycles; Monochromatic paths; Edge-recoloring costRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
-
Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme; Adria, Lyra; Protti, Fabio (2009) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Communication / Conférence
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Article accepté pour publication ou publié