LCS Publication Details
Publication Title: FAST DETERMINISTIC CONSTRUCTIONS OF LOW-DIAMETER NETWORK DECOMPOSITIONS
Publication Author: Berger, Bonnie
Additional Authors: Cowen, Lenore
LCS Document Number: MIT-LCS-TM-460
Publication Date: 12-1-1991
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
Finding a low-diameter decomposition of a network is one of the central problems in the theory of distributed systems. Many researchers have studied this problem in the hopes of obtaining improved distributed algorithms for maximal independent set, (?+1)-coloring, depth first search, all-pairs shortest paths, local routing, and distributed directories. We present here the fastest known deterministic distributed algorithm for the optimal decomposition of a network.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.