A nearly optimal distributed algorithm for computing the weighted girth  

作　　者：Qiang-Sheng HUA Lixiang QIAN Dongxiao YU Xuanhua SHI Hai JIN 

机构地区：[1]National Engineering Research Center for Big Data Technology and System/Services Computing Technology and System Lab/Cluster and Grid Computing Lab,School of Computer Science and Technology,Huazhong University oj Science and Technology,Wuhan 430074,China [2]Schoo I of Computer Science and Technology,Shandong University,Qingdao 266237,China

出　　处：《Science China(Information Sciences)》2021年第11期76-90,共15页中国科学（信息科学）（英文版）

基　　金：supported in part by National Key Research and Development Program of China(Grant No.2018YFB1003203);National Natural Science Foundation of China(Grants No.61972447);Fundamental Research Funds for the Central Universities(Grant No.2019kfy XKJC021)。

摘　　要：Computing the weighted girth, which is the sum of weights of edges in the minimum weight cycle,is an important problem in network analysis. The problem for distributively computing girth in unweighted graphs has garnered lots of attention, but there are few studies in weighted graphs. In this paper, we propose a distributed randomized algorithm for computing the weighted girth in weighted graphs with integral edge weights in the range [1, n^(c)], where n is the number of vertices and c is a constant. The algorithm is devised under the standard synchronous CON GE S T model, which limits each vertex can only transfer O(log n) bits information along each incident edge in a round. The upper bound of the algorithm is O(n log^(2) n) rounds. We also prove the lower bound for computing the weighted girth is Ω(D + n/log n) where D is the hop diameter of the weighted graph. This means our distributed algorithm is optimal within a factor of O(log^(3) n).

关 键 词：distributed algorithms weighted girth CON GE S T model communication complexity round complexity 

分 类 号：O157.5[理学—数学]