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 |