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最佳論文獎

聯系作者

文章來源：機器之心
作者微信：almosthuman2014
作者簡介：專業的人工智能媒體和產業服務平臺