Skip to content


Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Latest commit


Git stats


Failed to load latest commit information.
Latest commit message
Commit time
ecc version 1.1.2

This is the source code accompanying the paper

Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier:
Data reduction and exact algorithms for Clique Cover.
ACM Journal of Experimental Algorithmics, 13, Article 2.2, 15 pages, 2008.

Its purpose is to solve the Clique Cover problem, that is, to find a
minimum set of cliques in a graph such that every edge is covered by
at least one clique.

The program is written in Objective Caml and should be portable to any
supported system that provides the "Unix" module (only required for
timings). The current version can be obtained at It is distributed under
the terms of the GNU General Public License (GPL, see COPYING).

It has been tested on:

* Ubuntu GNU/Linux (amd64) 18.04.5 with Objective Caml 4.05.0

If you have the "make" utility (as any Unix system has), you can
compile with "make".

The program is called "ecc". By default, it reads a graph from
standard input and writes the cliques found to standard output. The
graph format is a simple text format, where each line describes one
edge, given by its two endpoints separated by whitespace:

v0 v1
v1 v2
v2 v0
v1 v3

Vertex names can be any combination of letters, digits, and _. Lines
starting with '#' are treated as comments. Note that this graph format
cannot describe degree-0 vertices; however, they are irrelevant for
covering cliques anyway.

The output is a set of cliques covering every edge of the graph. Each
line describes one clique by listing its vertices. Example:

$ ./ecc < example.graph 
v0 v1 v2
v1 v3

There are many options that affect program behavior; see ./ecc --help
for a listing.

Version history

1.0   initial release
1.1   minor changes
1.1.1 compile fix
1.1.2 URL updates

-- Falk Hüffner (
   9 August 2021


Solve the Clique Cover problem.







No releases published


No packages published