The Locality of Distributed Symmetry Breaking
Tóm tắt
Từ khóa
Tài liệu tham khảo
A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs/1408.2279 (2014). A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs/1408.2279 (2014).
R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + ε)-approximation for vertex cover in O(log Δ/εlog log Δ) rounds. CoRR abs/1602.03713 (2016). R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + ε)-approximation for vertex cover in O(log Δ/εlog log Δ) rounds. CoRR abs/1602.03713 (2016).
L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA. L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA.
D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge. D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.
M. Elkin , S. Pettie , and H. H. Su . 2015. (2Δ − 1)-edge coloring is much easier than maximal matching in the distributed setting . In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370 . M. Elkin, S. Pettie, and H. H. Su. 2015. (2Δ − 1)-edge coloring is much easier than maximal matching in the distributed setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370.
K. Kothapalli and S. V. Pemmaraju . 2012. Super-fast 3-ruling sets . In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs , Vol. 18 . Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 136--147. K. Kothapalli and S. V. Pemmaraju. 2012. Super-fast 3-ruling sets. In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, Vol. 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 136--147.
K. Kothapalli , C. Scheideler , M. Onus , and C. Schindelhauer . 2006. Distributed coloring in O˜(√log n) bit rounds . In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS). K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. 2006. Distributed coloring in O˜(√log n) bit rounds. In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS).
F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs/1011.5470 (2010). F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs/1011.5470 (2010).
C. St . J. A. Nash-Williams . 1964 . Decomposition of finite graphs into forests . J. London Math. Soc. 39 (1964), 12 . C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.
D. Peleg . 2000. Distributed Computing: A Locality-Sensitive Approach . SIAM , Philadelphia, PA . D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA.
R. Rubinfeld , G. Tamir , S. Vardi , and N. Xie . 2011. Fast local computation algorithms . In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238 . See also CoRR abs/1104.1377. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. 2011. Fast local computation algorithms. In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238. See also CoRR abs/1104.1377.