Locality in Distributed Graph Algorithms | |
| מחבר: Author: Автор: مؤلف: | Nathan Linial |
| הוצאה לאור: Published by: Издательство: دار نشر: | SIAM J. Comput. 21(1): 193-201 (1992) |
| An Omega(log*n) lower bound for finding an MIS in an oriented ring. | |
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms | |
| מחבר: Author: Автор: مؤلف: | Richard Cole and Uzi Vishkin |
| הוצאה לאור: Published by: Издательство: دار نشر: | STOC 1986: pages 206-219 |
| An O(log*n) algorithm for finding an MIS in an oriented ring. | |
A Simple Parallel Algorithm for the Maximal Independent Set Problem | |
| מחבר: Author: Автор: مؤلف: | Michael Luby |
| הוצאה לאור: Published by: Издательство: دار نشر: | SIAM J. Comput. 15(4): 1036-1053 (1986) |
| A randomized algorithm for finding an MIS in an arbitrary graph in O(logn) rounds. | |
Distributed Computing: A Locality-Sensitive Approach | |
| מחבר: Author: Автор: مؤلف: | David Peleg |
| הוצאה לאור: Published by: Издательство: دار نشر: | SIAM |
Additive spanners and (α, β)-spanners | |
| מחבר: Author: Автор: مؤلف: | Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie |
| הוצאה לאור: Published by: Издательство: دار نشر: | ACM Transactions on Algorithms (TALG), 7(1):5 (2010) |
| A construction of a (k,k-1)-spanner | |