About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Clique partitions, graph compression and speeding-up algorithms
Abstract
We first consider the problem of partitioning the edges of a graph G into 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 shown that the problem is NP-complete. We then prove the existence of a partition of small total order in a sufficiently dense graph and devise 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 compression for graphs of a given size. An interesting application of the graph compression result arises from the fact that several graph algorithms can be adapted to work with the compressed representation of the input graph, thereby improving the bound on their running times, particularly on dense graphs. This makes use of the trade-off result we obtain from our partitioning algorithm. The algorithms analyzed include those for matchings, vertex connectivity, edge connectivity, and shortest paths. In each case, we improve upon the running times of the best-known algorithms for these problems. © 1995 by Academic Press, Inc.