Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями

== Литература ==

1. Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary). In: Proc. of the 19th Annual ACM Symposium on Theory of Computing, pp. 230-240. ACM, USA (1987)

2. Boruvka, O.: Otakar Boruvka on minimum spanning tree problem (translation of both the 1926 papers, comments, history). Disc. Math. 233, 3-36 (2001)

3. Burns, J.E.: A formal model for message-passing systems. Indiana University, Bloomington,TR-91, USA (1980)

4. Frederickson, G., Lynch, N.: The impact of synchronous communication on the problem of electing a leader in a ring. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp. 493-503. ACM, USA (1984)

5. Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Prog. Lang. Systems 5(1), 66-77 (1983)

6. Johansen, K.E., Jorgensen, U.L., Nielsen, S.H.: A distributed spanning tree algorithm. In: Proc. 2nd Int. Workshop on Distributed Algorithms (DISC). Lecture Notes in Computer Science, vol. 312, pp. 1-12. Springer, Berlin Heidelberg (1987)

7. Korach, E., Moran, S., Zaks, S.: Tight upper and lower bounds for some distributed algorithms for a complete network of processors. In: Proc. 3rd Symp. on Principles of Distributed Computing (PODC), pp. 199-207. ACM, USA (1984)

8. Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. In: Proc. 4th Symp. on Principles of Distributed Computing (PODC), pp. 277-286. ACM, USA (1985)

9. Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput. 35(1), 120-131 (2005)

10. Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. Distrib. Comput. 18(6), 453^60 (2006)

11. Moses, Y., Shimony, B.: A new proof of the GHS minimum spanning tree algorithm. In: Distributed Computing, 20th Int. Symp. (DISC), Stockholm, Sweden, September 18-20, 2006. Lecture Notes in Computer Science, vol.4167, pp. 120-135. Springer, Berlin Heidelberg (2006)

12. Wu, B.Y., Chao, K.M.: Spanning Trees and Optimization Problems (Discrete Mathematics and Its Applications). Chapman Hall, USA (2004)