Next: MINIMUM K-CAPACITATED TREE PARTITION Up: Covering and Partitioning Previous: MINIMUM BOTTLENECK PATH MATCHING Index

### MINIMUM CLIQUE PARTITION

- 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