本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

Dec, 2013

针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。

Mar, 2022

本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。

Oct, 2023

本文通过研究贪婪顺序算法中迭代间的依赖结构，证明了随机排序后的贪婪最大独立集算法以及贪婪最大匹配算法的依赖深度为对数级别，提出了基于该结论设计的简单线性工作并行算法，该算法能在更高的并行度与更小的工作开销之间平衡，并且保证结果与顺序贪婪算法相同。

Feb, 2012

本文提出了一种新的最大权独立集问题分支和缩减策略，结合核心化与局部搜索能够比局部搜索单独得出更高质量的解，通过实验表明，在实践中这种方法比现有的算法更加有效，可以处理高达数百万个顶点和边的实际问题。

Oct, 2018

研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

Oct, 2020

通过引入一种新颖的无数据二次神经网络，该论文解决了最大独立集问题，并展示了与现有学习方法相比具有竞争力或更好性能的优势。

Jun, 2024

本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

Jul, 2019

本文提出一种基于图分割和并行二分图最大匹配的高效并行核化算法，通过依赖检查和约简跟踪技术加速核化，能够同时快速生成小内核，以及找到最小内核并加速发现最大独立集，取得比现有最快算法更小的内核大小和类似执行时间的优势。

Aug, 2017

该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

Jun, 2022