Article

Article title EXPERIMENTAL AND THEORETICAL EVALUATION OF PARALLEL ALGORITHM FOR FINDING MINIMAL SPANNING TREE ON CLUSTER SYSTEMS
Authors A.A. Al-Khulaidi, Y.O. Chernyshev
Section SECTION II. AUTOMATION OF DESIGNING
Month, Year 07, 2011 @en
Index UDC 004.032.24
DOI
Abstract This paper describes a parallel algorithm designed for finding the minimum spanning tree-based algorithm Boruvki Ratings and computational complexity of the proposed parallel algorithm. Computational experiments were carried out to assess the effectiveness of the parallel algorithm and Prim"s developed a parallel algorithm based on the method Boruvki. The comparative characteristics of the experimental and theoretical evaluations of parallel algorithms for finding a minimum spanning tree for cluster systems and a multiprocessor environment. The proposed parallel algorithms can achieve a significant amount of acceleration, including the use of several thousand processors. Comparative characteristics of the experimental and theoretical evaluations of parallel algorithms for finding the minimum spanning tree showed sufficient effectiveness of the developed parallel algorithm based on the method for finding Boruvki minimum spanning tree. This algorithm can be used to develop a parallel program for a cluster network or a multiprocessor system.

Download PDF

Keywords Method Boruvki; parallel programming; spanning tree.
References 1. Интернет-ресурс http://www.winhpc.ru/?id=138(дата обращения 12.12.2010).
2. Интернет-ресурс http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005(дата обращения 10.12.2010).
3. Аль-хулайди А.А. Разработка параллельного алгоритма для нахождения минимального остовного дерева // Шестнадцатая международная открытая научная конференция "Современные проблемы информатизации" издательство.– Воронеж: ВГТУ, 2011. – № 3. – С. 1-14.

Comments are closed.