Distributive graph algorithms Global solutions from local data
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 331-335
- https://doi.org/10.1109/sfcs.1987.20
Abstract
This paper deals with distributed graph algorithms. Processors reside in the vertices of a graph G and communicate only with their neighbors. The system is synchronous and reliable, there is no limit on message lengths and local computation is instantaneous. The results: A maximal independent set in an n-cycle cannot be found faster than Ω(log* n) and this is optimal by [CV]. The d-regular tree of radius r cannot be colored with fewer than √d colors in time 2r / 3. If Δ is the largest degree in G which has order n, then in time O(log*n) it can be colored with O(Δ2) colors.Keywords
This publication has 8 references indexed in Scilit:
- Ramanujan graphsCombinatorica, 1988
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Explicit construction of exponential sized families of k-independent setsDiscrete Mathematics, 1986
- Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithmsPublished by Association for Computing Machinery (ACM) ,1986
- Families of finite sets in which no set is covered by the union ofr othersIsrael Journal of Mathematics, 1985
- A simple parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1985
- A fast parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1984
- Intersections ofk-element setsCombinatorica, 1981