.png){kind=icon}
返回
Faster Combinatorial k-Clique Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1007/s00453-026-01390-8.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
检测一个图中是否包含k-团问题是计算机科学中最基本的问题之一。渐近最快的算法运行时间为O(n(ωk/3))，其中ω是布尔矩阵乘法的指数。迄今为止，这是唯一能够以多项式因子超越平凡O(n(k))界限的技术。由于该技术的各种局限性，人们付出了大量努力来设计通过其他技术改进穷举搜索的组合算法。本工作的第一个贡献是为k-团问题设计了一个更快的组合算法，将Vassilevska的O(n(k)/log(k-1)n)界限改进了两个对数因子。技术上，我们的主要成果是一种新的从k-团到三角形检测的约简，利用了Chan（SODA'15）和Yu（ICALP'15）近期组合算法的核心分治策略。本工作的第二个贡献是利用组合技术改进k-团问题的推广算法，包括非组合算法的最优结果。具体而言，我们引入了首个非平凡团列举算法：一个检测超图中团的一般算法，同时也改进了检测算法的最优结果；以及针对三角形列举特定情况的一个附加算法，并改进了其界限。
Keyword:
COMPLEXITY
