Detecting Cliques Using Degree and Connectivity Constraints

In graph mining determining clique is np complete problem. This paper introduces pruning strategies, by which linear time algorithm for detecting clique is obtained. Clique determination is widely applicable in social network analysis. In social network analysis cliques signifies that each person in the network knows every other person in the group. Here pruning is done using edge connectivity and degree constraints. Initially the graph (g) is checked for a bridge, if it is detected, then graph (g) is disconnected. Then minimum and maximum degree criteria are used to determine a clique. The algorithm also has wide application in bioinformatics.