Next:
MINIMUM K-CAPACITATED TREE PARTITION
Up:
Covering and Partitioning
Previous:
MINIMUM BOTTLENECK PATH MATCHING
 
Index
M
INIMUM
C
LIQUE
P
ARTITION
I
NSTANCE:
Graph
.
S
OLUTION:
A clique partition for
G
, i.e., a partition of
V
into disjoint subsets
such that, for
, the subgraph induced by
is a complete graph.
M
EASURE:
Cardinality of the clique partition, i.e., the number of disjoint subsets
.
Good News:
Equivalent to M
INIMUM
G
RAPH
C
OLORING
[
396
]. See results theirein.
Garey and Johnson:
GT15
Viggo Kann
2000-03-20