
A hypocoloring model for batch scheduling
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis; de Werra, Dominique (2005), A hypocoloring model for batch scheduling, Discrete Applied Mathematics, 146, 1, p. 3-26. http://dx.doi.org/10.1016/j.dam.2004.06.016
View/ Open
Type
Article accepté pour publication ou publiéDate
2005Journal name
Discrete Applied MathematicsVolume
146Number
1Publisher
Elsevier
Pages
3-26
Publication identifier
Metadata
Show full item recordAbstract (EN)
Starting from a batch scheduling problem, we consider a weighted subcoloring in a graph G; each node v has a weight w(v); each color class S is a subset of nodes which generates a collection of node disjoint cliques. The weight w(S) is defined as View the MathML source. In the scheduling problem, the completion time is given by View the MathML source where S=(S1,…,Sk) is a partition of the node set of graph G into color classes as defined above. Properties of such colorings concerning special classes of graphs (line graphs of cacti, block graphs) are stated; complexity and approximability results are presented. The associated decision problem is shown to be NP-complete for bipartite graphs with maximum degree at most 39 and triangle-free planar graphs with maximum degree k for any kgreater-or-equal, slanted3. Polynomial algorithms are given for graphs with maximum degree two and for the forests with maximum degree k. An (exponential) algorithm based on a simple separation principle is sketched for graphs without triangles.Subjects / Keywords
Approximability; Batch scheduling; Graph coloringRelated items
Showing items related by title and author.
-
Demange, Marc; de Werra, Dominique; Monnot, Jérôme; Paschos, Vangelis (2007) Article accepté pour publication ou publié
-
Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
-
Escoffier, Bruno; Demange, Marc; de Werra, Dominique; Milis, Ioannis; Lucarelli, Giorgio; Paschos, Vangelis; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Demange, Marc; de Werra, Dominique; Monnot, Jérôme; Paschos, Vangelis (2002) Communication / Conférence