The disjoint cliques problem

The disjoint cliques problem

0.00 Avg rating0 Votes
Article ID: iaor20001730
Country: France
Volume: 31
Issue: 1
Start Page Number: 45
End Page Number: 66
Publication Date: Jan 1997
Journal: RAIRO Operations Research
Authors: , ,
Keywords: scheduling
Abstract:

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, 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 time units, we look for a sequence of workers w1, ..., wk and a partition J1, ..., Jk of the job set such that Ji can be executed by wi within D time units. The goal is to find a sequence with minimum total wage of the workers.

Reviews

Required fields are marked *. Your email address will not be published.