Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328508 | Discrete Applied Mathematics | 2005 | 24 Pages |
Abstract
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 max{w(K)=âvâKw(v)|KâS}. In the scheduling problem, the completion time is given by âi=1kw(Si) 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 k⩾3. 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
D. de Werra, M. Demange, J. Monnot, V.Th. Paschos,