无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
作者:暮色微凉
时间:2025-02-10
浏览:9
谷歌博客放出新研究,求解无向图的最小割问题。1996年,美国计算机科学家DavidRKarger连同其他研究者在论文《Anewapproachtotheminimumcutproblem》中提出了一个令人惊讶的随机算法Karger算法,其在理论计算机科学中非常重要,尤其适用于大规模图的近似最小割问题。Karger算法可以在时间为O(mlog^3n)的图中找到一个最小割点,他们将这个时间称之为近线性时间,意思是线性乘以一个多对数因子。在谷歌刚刚更新的一篇博客中,他们介绍了之前发布的一篇论文《Determin
本文目录
谷歌博客放出新研究,求解无向图的最小割问题。

论文地址:https://arxiv.org/pdf/2401.05627.pdf 论文标题:Deterministic Near-Linear Time Minimum Cut in Weighted Graphs




作者最新文章
长网页转PDF怎么避免断图?网页转PDF怎么设置分页
2026-11-01 09:31
夸克资源库蓝光资源每日更新经典电视剧全集
2026-10-30 11:54
会声会影怎么导入音频 支持格式及步骤
2026-10-29 12:23
WPS表格常用功能实操:从录入到排序筛选的完整流程
2026-10-29 09:57
B站免费入口永久有效网址推荐
2026-10-28 16:37
下一篇:
PHP跨平台开发的持续集成与自动化部署
热门文章
更多
精品专题
更多
Mac软件
更多
WINDOWS
更多

































