Comparability graph augmentation for some multiprocessor scheduling problems Original Research Article

A comparability graph is a graph which admits a transitive orientation. In this paper we consider the problem of augmenting a graph to a comparability graph in such a way that the maximum weight of its cliques is minimum. The problem is equivalent to a multiprocessor scheduling problem and to the interval coloring problem; and in the unweighted case also to the chromatic number problem. In the general case, the problem is NP-hard in the strong sense even on some very simple types of perfect graphs. We give complexity and approximation results for two subclasses of perfect graphs, namely for split graphs and stars of cliques, for which the problem still remains intractable but admits efficient estimations.