The clique-partitioning problem

J. Bhasker, Tariq Samad

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

We study the problem of clique-partitioning a graph. We prove a new general upper bound result on the number of clique-partitions. This upper bound is the best possible, given information of just the vertices and the number of edges. Next we show that there exists an optimal partition in which one of the cliques is a maximal clique. Finally we present two new efficient methods to clique-partition a graph. Since the clique-partitioning of a graph is equivalent to the coloring of the complement of the graph, any coloring algorithm can also be used to clique-partition a graph. We present detailed statistics comparing the performance of our algorithms against two of the best known coloring algorithms and against a recently published clique-partitioning algorithm. Both functional and timing comparisons are given and we show that our algorithms compare very favorably on both counts.

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalComputers and Mathematics with Applications
Volume22
Issue number6
DOIs
StatePublished - 1991
Externally publishedYes

Fingerprint

Dive into the research topics of 'The clique-partitioning problem'. Together they form a unique fingerprint.

Cite this