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 a variety of different graph classes. We
give polynomial time algorithms for the problem
restricted to interval graphs, bipartite graphs,
cographs, directed path graphs and partial k-trees.
In contrast, we show the NP-completeness for undirected
path graphs. Moreover, we investigate a closely related
scheduling problem.
