版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Department of Computer Science University of Houston HoustonTX United States Department of Computing and Software McMaster University Hamilton Canada School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm Sweden
出 版 物:《Bulletin of the European Association for Theoretical Computer Science》 (Bull. Eur. Assoc. Theor. Comput. Sci.)
年 卷 期:2018年第2018卷第125期
核心收录:
学科分类:08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:Coun-Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672
摘 要:This article surveys the distributed minimum spanning tree (MST) problem, a central and one of the most studied problems in distributed computing. In this problem, we are given a network, represented as a weighted graph G = (V, E), and the nodes in the network communicate by message passing via the edges of G with the goal of constructing an MST of G in a distributed fashion, i.e., each node should identify the MST edges incident to itself. This article summarizes the long line of research in designing efficient distributed algorithms and showing lower bounds for the distributed MST problem, including the most recent developments which have focused on algorithms that are simultaneously round-and message-optimal. © 2018, European Association for Theoretical Computer Science. All rights reserved.