Distributed Graph Algorithms and their Complexity : An Introduction (Special issue: Reviews and lectures : exploring the limits of computation II)
Taisuke Izumi · Institutional Repositories DataBase (IRDB) · 2015
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.