首页    期刊浏览 2024年11月29日 星期五
登录注册

文章基本信息

  • 标题:Algorithm to Find All Cliques in a Graph
  • 本地全文:下载
  • 作者:A. Ashok Kumar ; S. Athisayanathan ; A. Antonysamy
  • 期刊名称:International Journal of Advanced Networking and Applications
  • 电子版ISSN:0975-0290
  • 出版年度:2010
  • 卷号:2
  • 期号:2
  • 页码:597-601
  • 出版社:Eswar Publications
  • 摘要: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 b y the set A is a cliq ue 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 co mplexities
  • 关键词:adjacency matrix; binary count; clique; powerset; subset
国家哲学社会科学文献中心版权所有