Evènement pour le groupe GT Graphes et Applications

Date 2012-05-11  14:00-15:00
TitreComplexity and algorithms for max-coloring problems 
RésuméWe deal with generalizations of the classical graph edge/vertex-coloring problems motivated by scheduling questions arising in computer and communication systems. The most general problems we attack are called bounded max-edge/vertex-coloring 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) max-coloring problems. The max-coloring problems have been well motivated and studied in the literature. Max-edge-coloring problems arise in switch based communication systems, like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Max-vertex-coloring 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, max-coloring 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 max-coloring problems. In this talk, we present complexity results as well as algorithms for the bounded max-edge/vertex-coloring problems.  
LieuSalle 178 
OrateurGiorgio Lucarelli 

Aucun document lié à cet événement.

Retour à l'index