• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles

Thumbnail
Date
2015
Dewey
Recherche opérationnelle
Sujet
Edge-colored graphs; Properly edge-colored paths; Trails and cycles; Monochromatic paths; Edge-recoloring cost
JEL code
C.C4.C44
Journal issue
Theoretical Computer Science
Volume
602
Publication date
10-2015
Article pages
89-102
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2015.08.016
URI
https://basepub.dauphine.fr/handle/123456789/16122
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Luerbio, Faria
status unknown
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Martinhon, Carlos A.
status unknown
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.