我们实现了一种新算法来列举稀疏图中所有的极大团,并在大量的真实世界图形语料库上分析了其性能。我们的分析表明,该算法是第一个为列举大型稀疏图中所有极大团提供实用解决方案的算法。
Mar, 2011
本研究提出了一种基于新颖的修剪技术的精确算法,能够在大型稀疏图中快速找到最大团。实验结果表明,在大多数情况下,我们的算法比现有算法快数个数量级,并且我们还提出了一种能够在最优或接近最优解的情况下比精确算法快数个数量级的启发式变体。
Sep, 2012
本文介绍了一种用于在具有小 $k$ 的连通 $k$-plexes 中列出所有最大 $k$-plex 的算法,改进了所有先前已知的结果,同时还提供了几种用于加速算法的技术,实际结果表明,该方法的性能优于现有技术。
Feb, 2022
本研究探讨图上极小分离集合的最大个数,给出了该个数的上界和下界,并使用简单和基础的证明方式,同时提出对图中潜在的最大团的改进下界。
Mar, 2015
提出了一种精确算法,通过定义输入实例的新参数,即度退化界限和给定图中最大 k-plex 的大小之间的差距 gk (G),并将其参数化,使算法在输入图的大小多项式时间内运行,对于真实世界中的图,gk (G) 通常很小,有界于 O (log (|V|)),表明算法在多项式时间内运行。
Jun, 2023
文章研究了在时间网中找到特定类型的社区(Delta-k-plexes),并提出了一种递归算法来枚举所有的最大 Delta-k-plexes,其中 Delta-1-plexes(即 Delta-cliques)比之前的算法更快。
Jun, 2018
研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务,其中低次多项式算法可以找到半优大小的独立集,但不大于此规模。
Oct, 2020
本文提出了一种几乎最优的亚线性时间算法,可用于在图中近似估计最小顶点覆盖大小。该算法可询问所选顶点的度 deg (v),以及每个 1<=i<=deg (v) 的 i-th 邻居。它的查询复杂度和运行时间约为 O (avg_deg*poly (1/epsilon)),其中 avg_deg 是图中平均顶点度数。对于密集图,我们考虑另一种模型,其中算法可以询问任何一对顶点 u 和 v 之间是否存在边,并获得了一个能输出 (2,epsilon) 近似最小顶点覆盖大小,其查询复杂度和运行时间约为 O (n)*poly (1/epsilon)。
Oct, 2011
提出了一种使用新的修剪技术的确切算法,可快速在非常大、稀疏的图中找到最大团,并提出了一个快得多且提供最优或接近最优解的启发式算法,同时在网络中检测重叠社区的开发方法。
Nov, 2014
本文提出了一种新的算法,能在近线性时间内解决 Erdos-Renyi 随机图中的大小不小于 (1+eps) sqrt (N/e) 的 clique 识别问题,并在大环正则图的情况下通过 “local” 算法成功识别大小不小于 (1+eps) N/sqrt (eDelta) 的 clique。
Apr, 2013