文章基本信息

标题：Distributed Graph Algorithms and their Complexity: An Introduction
本地全文：下载
作者：Taisuke IZUMI
期刊名称：Interdisciplinary Information Sciences
印刷版ISSN：1340-9050
电子版ISSN：1347-6157
出版年度：2015
卷号：21
期号：4
页码：351-370
DOI：10.4036/iis.2015.L.04
出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：Distributed graph algorithms are the methods for solving graph problems defined over networks of computers, where each vertex is a computing entity (i.e., process) and an edge is a communication link between two processes. This introductory survey presents a brief outline, several important concepts, and the fundamental complexity study of distributed graph algorithms. For a number of standard problems such as the shortest path and the coloring, we spotlight their inherent difficulties and challenges.
关键词：distributed algorithms;graph algorithms;computational complexity