Using Symbolic Techniques to find the Maximum Clique in Very Large Sparse Graphs
ED&TC95: IEEE European Design and Test Conference, Paris, March 1995
ABSTRACT
Several problems arising in CAD for VLSI, espe-cially in logic and high level synthesis, are modeled as graph-theoretical problems. In particular, minimization problems often require the knowledge of the cliques in a graph. This paper presents a new approach for find-ing the maximum clique in realistic graphs. The algorithm is built around a classical branch-and-bound, but exploits the efficiency of Binary Decision Dia-grams and Symbolic Techniques to avoid explicit enumeration of the search space. The approach is proven to be more efficient than classical algorithms, which suffer from the enumeration problem, as well as than purely symbolic implementations, which suffer from the explosion in the size of BDDs. As a result, we are able to compute the maximum clique without introducing approximations for graphs with billions of vertices and transitions.
| Related files: | |
|---|---|
| edtc95c.pdf | Adobe Acrobat portable document |
| edtc95c.ps.gz | postscript document, compressed (with gzip) |
Copyright note for papers published by the IEEE Computer Society:
Copyright IEEE. Personal use of this material is permitted. However,
permission to reprint/republish this material for advertising or
promotional purposes or for creating new collective works for resale
or redistribution to servers or lists, or to reuse any copyrighted
component of this work in other works, must be obtained from the IEEE.
[CPSe95] F. Corno, P. Prinetto, M. Sonza Reorda, "Using Symbolic Techniques to find the Maximum Clique in Very Large Sparse Graphs," ED&TC95: IEEE European Design and Test Conference, Paris, March 1995