Summary: Given a graph $G= (V,E)$, we consider the problem of finding a set of $D$ pairwise disjoint cliques in the graph with maximum overall number of vertices. We determine the computational complexity of this problem restricted to variety of different graph classes. We give polynomial time algorithms for the problem restricted to interval graphs, cographs, directed path graphs and partial $k$-trees. In contrast, we show the NP-completeness of this problem for undirected path graphs. Moreover, we investigate a closely related scheduling problem. Given $D$ times units, we look for a sequence of workers $w_1,\dots,w_k$ and a partition $J_1,\dots,J_k$ of the job set such that $J_i$ can be executed by $w_i$ within $D$ time units. The goal is to find a sequence with minimum total wage of the workers.
|90C35||Programming involving graphs or networks|
|90B35||Scheduling theory, deterministic|
|90C60||Abstract computational complexity for mathematical programming problems|