The idea of this paper is to speed up some graph algorithms by using a compressed representation of the graph. This representation is constructed by partitioning the graph into bipartite cliques, each of which is replaced by a tree. The number of edges is thereby reduced, although the path structure of the original graph is maintained. Thus, the technique can be applied to graph problems whose solution mainly depends on the graph structure, such as all-pairs shortest paths, matching, edge connectivity, and vertex connectivity. Roughly speaking, the running time of these algorithms can be improved by a logarithmic factor.

The authors first consider the problem of partitioning a graph into bipartite cliques. Their algorithm is based on the fact that every sufficiently dense graph contains a large clique and this clique can be determined efficiently. The algorithm is repeated until the density of the remaining graph is no longer sufficient.

Although this paper is a conference contribution with limited space, it is clearly written and the algorithms are transparent. The proofs concerning clique partitioning are given in detail; the other proofs are only sketched out and deferred to a final version. The paper is of interest for specialists in graph theory and the complexity of algorithms.