無向圖最小割問題取得新突破，谷歌研究獲SODA 2024最佳論文獎

AIGC動態(tài)歡迎閱讀

原標(biāo)題：無向圖最小割問題取得新突破，谷歌研究獲SODA 2024最佳論文獎
關(guān)鍵字：最小,算法,線性,時間,權(quán)重
文章來源：機器之心
內(nèi)容字?jǐn)?shù)：5390字

內(nèi)容摘要：

機器之心報道
機器之心編輯部谷歌博客放出新研究，求解無向圖的最小割問題。1996 年， 美國計算機科學(xué)家 David R Karger 連同其他研究者在論文《 A new approach to the minimum cut problem》中提出了一個令人驚訝的隨機算法 Karger 算法，其在理論計算機科學(xué)中非常重要，尤其適用于大規(guī)模圖的近似最小割問題。
Karger 算法可以在時間為 O (m log^3n) 的圖中找到一個最小割點，他們將這個時間稱之為近線性時間，意思是線性乘以一個多對數(shù)因子。
在谷歌剛剛更新的一篇博客中，他們介紹了之前發(fā)布的一篇論文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研究獲得了 ACM-SIAM SODA24 最佳論文獎。文章詳細(xì)闡述了一個幾乎是線性時間內(nèi)（而不是近線性時間）運行的新算法，這個算法是確定性的，能夠可靠地找到正確的最小割，改進(jìn)了之前可能無法保證結(jié)果正確或只適用于簡單圖的算法。可以說這是自 Karger 著名的隨機化算法以來的重大發(fā)現(xiàn)。論文地址：htt

原文鏈接：無向圖最小割問題取得新突破，谷歌研究獲SODA 2024最佳論文獎

聯(lián)系作者

文章來源：機器之心
作者微信：almosthuman2014
作者簡介：專業(yè)的人工智能媒體和產(chǎn)業(yè)服務(wù)平臺