MINIMUM CLIQUE PARTITION

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

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A clique partition for G, i.e., a partition of V into disjoint subsets $V_1,V_2,\ldots,V_k$ such that, for $1\le i\le k$ , the subgraph induced by is a complete graph.
MEASURE: Cardinality of the clique partition, i.e., the number of disjoint subsets .
Good News: Equivalent to MINIMUM GRAPH COLORING [396]. See results theirein.
Garey and Johnson: GT15

Viggo Kann
2000-03-20