Algorithm to Find All Cliques in a Graph
Journal: International Journal of Advanced Networking and Applications (Vol.2, No. 02)Publication Date: 2010-09-06
Authors : A. Ashok Kumar; S. Athisayanathan; A. Antonysamy;
Page : 597-601
Keywords : Adjacency matrix; binary count; clique; powerset; subset;
Abstract
-Let V = {1, 2, 3, . . . , n} be the vertex set of a graph G, P(V ) the powerset of V and A β P(V ). Then A can be represented as an ordered n-tuple (x1x2x3 . . .xn) where xi = 1 if i β A, otherwise xi = 0 (1 ? i ? n). This representation is called binary count (or BC) representation of a set A and denoted as BC(A). Given a graph G of order n, it is shown that every integer m in S = {0, 1, 2, . . . , 2n - 1} corresponds to a subset A of V and vice versa. We introduce algorithms to find a subset A of the vertex set V = {1, 2, 3, . . . , n} of a graph G that corresponds to an integer m in S = {0, 1, 2, . . . , 2n - 1}, verify whether A is a subset of any other subset B of V and also verify whether the sub graph < A > induced by the set A is a clique or not using BC representation. Also a general algorithm to find all the cliques in a graph G using BC representation is introduced. Moreover we have proved the correctness of the algorithms and analyzed their time complexities.
Other Latest Articles
- Intelligent Methods of Fusing the Knowledge During Incremental Learning via Clustering In A Distributed Environment
- A Survey of Energy-Efficient Hierarchical Cluster-Based Routing in Wireless Sensor Networks
- Transmission Techniques for Ultra Dense Wavelength Division Multiplexing By Using Two Optical Amplifiers in Nonlinear Optical Networks
- Defending Denial of Service: State Overload Attacks
- Evaluation of Feature Selection Methods for Predictive Modeling Using Neural Networks in Credits Scoring
Last modified: 2015-12-04 19:28:15