CLIQUE PARTITIONS, GRAPH COMPRESSION AND SPEEDING-UP ALGORITHMS

We first consider the problem of partitioning the edges of a graph G i nto bipartite cliques such the total order of the cliques is minimized , where the order of a clique is the number of vertices in it. It is s hown that the problem is NP-complete. We then prove the existence of a partition of small total order in a sufficiently dense graph and devi se an efficient algorithm to compute such a partition and the running time. Next, we define the notion of a compression of a graph G and use the result on graph partitioning to efficiently compute an optimal co mpression for graphs of a given size. An interesting application of th e graph compression result arises from the fact that several graph alg orithms can be adapted to work with the compressed representation of t he input graph, thereby improving the bound on their running times, pa rticularly on dense graphs. This makes use of the trade-off result we obtain from our partitioning algorithm. The algorithms analyzed includ e those for matchings, vertex connectivity, edge connectivity, and sho rtest paths. In each case, we improve upon the running times of the be st-known algorithms for these problems. (C) 1995 Academic Press, Inc.