本研究提出了一种基于新颖的修剪技术的精确算法,能够在大型稀疏图中快速找到最大团。实验结果表明,在大多数情况下,我们的算法比现有算法快数个数量级,并且我们还提出了一种能够在最优或接近最优解的情况下比精确算法快数个数量级的启发式变体。
Sep, 2012
该论文提出了一种快速、并行的最大团算法,特别适用于求解大型稀疏图,具备线性运行时特性,并且采用巧妙的预剪枝和分支策略,通过核心数和启发式算法发现关键点,同时使用并行搜索树加速探索;应用该算法计算强时间连通性和压缩图。
Feb, 2013
该研究提出了一种基于机器学习的框架来扩大组合优化算法,并使用可解释的学习模型来提供更深层次的洞见,以设计更好的启发式方法,在最大团枚举问题中展示了该框架的性能,并从中获得启示设计了一种新的启发式方法。
Jan, 2020
提出了一种使用新的修剪技术的确切算法,可快速在非常大、稀疏的图中找到最大团,并提出了一个快得多且提供最优或接近最优解的启发式算法,同时在网络中检测重叠社区的开发方法。
Nov, 2014
本文提出了一个简单,强大和灵活的机器学习框架,用于减少计算困难的集合问题的枚举变量搜索空间,并通过输入分布产生的信息提示来增强现有的最先进的求解器。我们将我们的框架实例化为图中列出所有最大团的问题,这是网络分析,数据挖掘和计算生物学中的中心问题。我们证明了我们的方法在具有数百万个顶点和边的真实世界网络上的实用性,不仅保留了所有最优解,而且还积极剪枝输入实例大小,导致比最先进的算法快几倍。最后,我们探讨了我们提出的框架的可扩展性和鲁棒性的限制,表明监督学习在实践中应用于 NP-hard 问题是可行的。
Feb, 2019
我们实现了一种新算法来列举稀疏图中所有的极大团,并在大量的真实世界图形语料库上分析了其性能。我们的分析表明,该算法是第一个为列举大型稀疏图中所有极大团提供实用解决方案的算法。
Mar, 2011
这篇论文对最大团问题进行了全面的综述,介绍了解决该问题的经典算法,并对图神经网络和量子算法的最新发展进行了回顾,并提供了用于测试经典、新学习和量子算法的基准。
Mar, 2024
本文提出的随机剪枝方法(称为 “子模函数稀疏化(SS)”)能够减少子模最大化的成本,并在新闻与视频摘要任务中显著降低计算成本和内存使用率,同时保持(甚至略微超过)处理原始数据集的成果。
Jun, 2016
通过比较两种基于多核线程并行的最大团问题的分支定界算法的并行适应性,进一步提出了一种低开销、可扩展的工作分割机制,并通过解释并行搜索顺序和搜索空间内解的可能位置之间的交互来说明成功的原因。
Jan, 2014
本文介绍了一种用于在具有小 $k$ 的连通 $k$-plexes 中列出所有最大 $k$-plex 的算法,改进了所有先前已知的结果,同时还提供了几种用于加速算法的技术,实际结果表明,该方法的性能优于现有技术。
Feb, 2022