| Abstrakt: |
Abstract??A version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problems: each nodevof a graphGcorresponds to some operation to be processed (with a processing timew(v)), edges represent nonsimultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot, all operations assigned to this slot are compatible; the length of a time slot will be the maximum of the processing times of its operations. The numberkof time slots to be used has to be determined as well. So, we have to find ak-coloring$${\cal s}$$=$$({s_{1},\ldots ,s_{k}})$$ofGsuch thatw(S1) + ?s+w(Sk) is minimized wherew(Si) = max {w(v) :v∊V}. Properties of optimal solutions are discussed, and complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to beNP-complete for bipartite graphs, for line-graphs of bipartite graphs, and for split graphs. [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink