<p>You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just coded this in C++ for some project that I'm working on now. I can share the code if you'd like it (it accepts DIMACS files).</p>

CC BY-SA 3.0
2014-03-17T01:35:23.597Z
It's fine I ended up coding it myself yesterday. But thanks :)
m09
CC BY-SA 3.0
2014-03-16T18:41:58.643Z
2014-03-16T18:41:58.643Z
Stas Busygin
<p>I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.</p>

<p>I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a maximal solution (ie 1 clique per edge on an edge cover).</p>

<p>Any pointer towards a nice algorithm?</p>

CC BY-SA 3.0
2014-03-16T06:07:00.400Z
This is usually studied as a conventional colouring problem on the complement of the graph instead ... as you probably know, there are many fast (somewhat intelligent greedy-styled) colouring algorithms which are fast. If the vast literature on graph colouring does not cover what you are looking for, you might need to be more specific as to what sort of attributes an algorithm you are looking for should have.
JimN
CC BY-SA 3.0
2014-03-16T22:15:13.170Z
Coloring is [inapproximable within](http://theoryofcomputing.org/articles/v003a006/) $n^{1-\epsilon}$ for any $\epsilon>0$. [DSATUR](https://www.google.com/search?q=dsatur&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a&channel=fflb) is a commonly used heuristic. There's a [linear-time algorithm](http://dl.acm.org/citation.cfm?doid=2402.322385) for finding a coloring using [degeneracy](http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29)+1 colors.
Austin Buchanan
<graph-theory><clique>
Fast approximation of (vertex) clique cover
m09
# Fast approximation of (vertex) clique cover

(Asked by: username_0 on 2014-03-16)

I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.

I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a maximal solution (ie 1 clique per edge on an edge cover).

Any pointer towards a nice algorithm?

**Tags:** graph-theory, clique

> **Comments:**
> **username_1**: This is usually studied as a conventional colouring problem on the complement of the graph instead ... as you probably know, there are many fast (somewhat intelligent greedy-styled) colouring algorithms which are fast. If the vast literature on graph colouring does not cover what you are looking for, you might need to be more specific as to what sort of attributes an algorithm you are looking for should have.  
> **username_2**: Coloring is [inapproximable within](http://theoryofcomputing.org/articles/v003a006/) $n^{1-\epsilon}$ for any $\epsilon>0$. [DSATUR](https://www.google.com/search?q=dsatur&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a&channel=fflb) is a commonly used heuristic. There's a [linear-time algorithm](http://dl.acm.org/citation.cfm?doid=2402.322385) for finding a coloring using [degeneracy](http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29)+1 colors.  

---

## 1 answers

### Answer by username_3 on 2014-03-16. Score: 2 | Accepted answer

You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just coded this in C++ for some project that I'm working on now. I can share the code if you'd like it (it accepts DIMACS files).

> **Comments:**
> **username_0**: It's fine I ended up coding it myself yesterday. But thanks :)  

---

