Scholarlink

<p>We study the clique problem on partite graphs. As a special type of clique, cliques on <i>k</i>-partite graphs have extensive applications in areas such as gene data analysis, data classification, protein function determination, recommendation systems, and social network analysis. However, existing research has largely focused on the maximum clique problem on <i>k</i>-partite graphs, neglecting other commonly occurring clique structures. To address this gap, for the first time, we define three special clique structures on <i>k</i>-partite graphs and analyze their interrelationships. We also formulate the clique enumeration problem on <i>k</i>-partite graphs and perform a comprehensive complexity analysis. Furthermore, we propose an efficient clique enumeration algorithm that takes advantage of the unique properties of cliques on <i>k</i>-partite graphs and integrates various techniques, such as pruning strategies and ordered sets, to accelerate the enumeration process. Experimental results on four real-world <i>k</i>-partite graphs validate the efficiency of the proposed algorithm and the effectiveness of the techniques employed.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Enumerating Cliques on k-Partite Graphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月28日

查看全文
  • Faming Li,
  • Shengli Qiu,
  • Baoling Ning,
  • Xiaochun Yang,
  • Bin Wang,
  • Jianzhong Li

摘要

We study the clique problem on partite graphs. As a special type of clique, cliques on k-partite graphs have extensive applications in areas such as gene data analysis, data classification, protein function determination, recommendation systems, and social network analysis. However, existing research has largely focused on the maximum clique problem on k-partite graphs, neglecting other commonly occurring clique structures. To address this gap, for the first time, we define three special clique structures on k-partite graphs and analyze their interrelationships. We also formulate the clique enumeration problem on k-partite graphs and perform a comprehensive complexity analysis. Furthermore, we propose an efficient clique enumeration algorithm that takes advantage of the unique properties of cliques on k-partite graphs and integrates various techniques, such as pruning strategies and ordered sets, to accelerate the enumeration process. Experimental results on four real-world k-partite graphs validate the efficiency of the proposed algorithm and the effectiveness of the techniques employed.