Sep, 2012

大规模稀疏图上最大团问题的快速算法

PDF
TL;DR本研究提出了一种基于新颖的修剪技术的精确算法，能够在大型稀疏图中快速找到最大团。实验结果表明，在大多数情况下，我们的算法比现有算法快数个数量级，并且我们还提出了一种能够在最优或接近最优解的情况下比精确算法快数个数量级的启发式变体。
maximum clique problemnp-hardexact algorithmpruning techniqueslarge sparse graphs
发现论文，激发创造
  • 大规模图上最大团问题的快速算法及其在重叠社团检测中的应用

    提出了一种使用新的修剪技术的确切算法，可快速在非常大、稀疏的图中找到最大团，并提出了一个快得多且提供最优或接近最优解的启发式算法，同时在网络中检测重叠社区的开发方法。

    Nov, 2014

  • 并行极大团算法及其在网络分析和存储方面的应用

    该论文提出了一种快速、并行的最大团算法，特别适用于求解大型稀疏图，具备线性运行时特性，并且采用巧妙的预剪枝和分支策略，通过核心数和启发式算法发现关键点，同时使用并行搜索树加速探索；应用该算法计算强时间连通性和压缩图。

    Feb, 2013

  • 大规模稀疏现实世界图中列出所有极大团

    我们实现了一种新算法来列举稀疏图中所有的极大团，并在大量的真实世界图形语料库上分析了其性能。我们的分析表明，该算法是第一个为列举大型稀疏图中所有极大团提供实用解决方案的算法。

    Mar, 2011

  • 多阶段稀疏化学习用于极大团枚举

    本文提出一种多阶段学习方法，用于枚举最大团子集的搜索空间修剪，并展示其在不同领域图实例上的良好表现。

    Sep, 2019

  • 最大团问题的新方法综述：从经典算法到图神经网络和量子算法

    这篇论文对最大团问题进行了全面的综述，介绍了解决该问题的经典算法，并对图神经网络和量子算法的最新发展进行了回顾，并提供了用于测试经典、新学习和量子算法的基准。

    Mar, 2024

  • 基于配对约束的可实践最大团算法

    本文提出了一种非常高效的最大团算法，通过组合策略和基于图着色的边界和修剪，解决了匹配的成对约束问题，从而解决了三维点云配准中的问题。

    Feb, 2019

  • 组合优化中的细粒度搜索空间剪枝和启发式学习

    该研究提出了一种基于机器学习的框架来扩大组合优化算法，并使用可解释的学习模型来提供更深层次的洞见，以设计更好的启发式方法，在最大团枚举问题中展示了该框架的性能，并从中获得启示设计了一种新的启发式方法。

    Jan, 2020

  • 在稀疏图中列出所有极大团在近优时间内

    该论文研究了 $n$ 个顶点的图的退化度，提出了基于 Bron-Kerbosch 算法的近似最优固定参数可跟踪算法，用以枚举所有最大团，并给出算法的时间复杂度、最大团的数量及匹配的上下界。

    Jun, 2010

  • 最大团问题的搜索树形状及其对并行分支界限的影响

    通过比较两种基于多核线程并行的最大团问题的分支定界算法的并行适应性，进一步提出了一种低开销、可扩展的工作分割机制，并通过解释并行搜索顺序和搜索空间内解的可能位置之间的交互来说明成功的原因。

    Jan, 2014

  • 组合近似聚类删除：更简单、更快、更好

    删除最小数量的边将图划分为团体是一种 NP 困难的图聚类目标，在计算生物学和社交网络分析中具有应用。我们提供了两种先前近似算法的更严格的分析，将其近似保证从 4 改进到 3。此外，我们展示了这两种算法可以以出人意料的简单方式解除随机化，通过在辅助图中贪婪地选择具有最大度的顶点并围绕其形成一个聚类。其中一种算法依赖于解决一个线性规划问题。我们最后的贡献是设计一种新的纯组合方法来解决这个问题，在理论和实践中更加可扩展。

    Apr, 2024