Next: MINIMUM K-CAPACITATED TREE PARTITION
Up: Covering and Partitioning
Previous: MINIMUM BOTTLENECK PATH MATCHING
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A clique partition for G, i.e., a partition of V into disjoint subsets
such that, for
,
the subgraph induced by
Vi is a complete graph.
- MEASURE:
Cardinality of the clique partition, i.e., the number of disjoint subsets
Vi.
- Good News:
Equivalent to MINIMUM GRAPH COLORING [374].
See results theirein.
- Garey and Johnson: GT15
Viggo Kann
1999-04-22