
Evènement pour le groupe GT Graphes et Applications
Date  20120511 14:0015:00 
Titre  Complexity and algorithms for maxcoloring problems 
Résumé  We deal with generalizations of the classical graph edge/vertexcoloring problems motivated by scheduling questions arising in computer and communication systems. The most general problems we attack are called bounded maxedge/vertexcoloring problems and take as input an edge/vertex weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest edge/vertex in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) maxcoloring problems. The maxcoloring problems have been well motivated and studied in the literature. Maxedgecoloring problems arise in switch based communication systems, like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Maxvertexcoloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Moreover, maxcoloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of the bounded maxcoloring problems. In this talk, we present complexity results as well as algorithms for the bounded maxedge/vertexcoloring problems. 
Lieu  Salle 178 
Orateur  Giorgio Lucarelli 
Email  glucarelli@gmail.com 
Url  LIP6, UPMC 
Aucun document lié à cet événement. RetourRetour à l'index
 