1989 · 302 citations · 13 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsTheory Of ComputationAlgorithm AnalysisDistributed AlgorithmsDistributed ComputingGraph AlgorithmsGraph ColoringGraph TheoryComputational Complexity Of Graph AlgorithmsDistributed Coloring AlgorithmsGraph DecompositionsMaximum Independent Set ApproximationNetwork Decomposition
The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n/sup epsilon /) time for epsilon =O((log log n/log n)/sup 1/2/), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
13
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations
Complexity of network synchronization
Baruch Awerbuch · Journal of the ACM · 1985 · 691 citations · Full text