无向图最小割问题取得新突破，谷歌研究获SODA 2024最佳论文奖（无向图 pagerank）

AIGC动态欢迎阅读

原标题：无向图最小

割问题取得新突破，谷歌研究获SODA 2024最佳论文奖

文章来源：机器之心

内容字数：5390字

内容摘要：

机器之心报道

机器之心编辑部谷歌博客放出新研究，求解无向图的最小割问题。1996 年，美国计算机科学家 David R Karger 连同其他研究者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法，其在理论计算机科学中非常重要，尤其适用于大规模图的近似最小割问题。

Karger 算法可以在时间为 O (m log^3n) 的图中找到一个最小割点，他们将这个时间称之为近线性时间，意思是线性乘以一个多对数因子。

在谷歌刚刚更新的一篇博客中，他们介绍了之前发布的一篇论文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研究获得了 ACM-SIAM SODA24 最佳论文奖。文章详细阐述了一个几乎是线性时间内（而不是近线性时间）运行的新算法，这个算法是确定性的，能够可靠地找到正确的最小割，改进了之前可能无法保证结果正确或只适用于简单图的算法。可以说这是自 Karger 著名的随机化算法以来的重大发现。论文地址：htt

原文链接：无向图最小割问题取得新突破，谷歌研究获SODA 2024最佳论文奖