THE DISJOINT CLIQUES PROBLEM

Citation
K. Jansen et al., THE DISJOINT CLIQUES PROBLEM, RAIRO. Recherche operationnelle, 31(1), 1997, pp. 45-66
Citations number
19
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
ISSN journal
03990559
Volume
31
Issue
1
Year of publication
1997
Pages
45 - 66
Database
ISI
SICI code
0399-0559(1997)31:1<45:TDCP>2.0.ZU;2-9
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 o f 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, cograf ts, directed path graphs and partial k-trees. In contrast, we show ril e NP-completeness of this problem for undirected path graphs. Moreover , we investigate a closely related scheduling problem. Given D times u nits, we look for a sequence of workers w(1),...,w(k) and a partition J(1),...,J(k) of the job set such that J(i) can be executed by w(i) wi thin D time limits. The goal is to find a sequence with minimum total wage of the workers.