Seminario Interdipartimentale di Algoritmica  

Monday, December 05, 2005, 12:00 noon
Complexity and Approximation of Some Weighted Coloring Problems
Bruno Escoffier, Université Paris Dauphine

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

Coloring a graph consists in giving each vertex a color such that two adjacent vertices do not have the same color. Here, we consider two generalizations of this well known graph problem. In the first one, called Min Weighted Coloring, we assume that each vertex has an integer weight. The goal is to color the graph in order to minimize the sum of the color weights, where the weight of a color is the weight of the heaviest vertex of this color. In the second one, we deal with probabilistic combinatorial optimization, which is a general framework trying to model situations where the instance of the problem is not known in advance. We apply this model to the coloring problem. In both cases, we present some complexity and polynomial approximation results, mainly on simple classes of graphs, such as bipartite or split graphs.