A NEW PARALLEL ALGORITHM FOR COMPUTING MINIMUM SPANNING TREE
| Main Authors: | M. I. Moussa, E. M. Badr |
|---|---|
| Format: | Article Journal |
| Bahasa: | eng |
| Terbitan: |
, 2013
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/1283745 |
| ctrlnum |
1283745 |
|---|---|
| fullrecord |
<?xml version="1.0"?>
<dc schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd"><creator>M. I. Moussa</creator><creator>E. M. Badr</creator><date>2013-05-31</date><description> Computing the minimum spanning tree of the graph is one of the fundamental computational problems. In this paper, we present a new parallel algorithm for computing the minimum spanning tree of an undirected weighted graph with vertices and edges. This algorithm uses the cluster techniques to reduce the number of processors by fraction and the parallel work by the fraction O ( 1 lo g ( f ( n )) ),where f (n) is an arbitrary function. In the case f (n) =1, the algorithm runs in logarithmic-time and use super linear work on EREWPRAM model. In general, the proposed algorithm is the simplest one.</description><identifier>https://zenodo.org/record/1283745</identifier><identifier>10.5281/zenodo.1283745</identifier><identifier>oai:zenodo.org:1283745</identifier><language>eng</language><relation>doi:10.5281/zenodo.1283744</relation><rights>info:eu-repo/semantics/openAccess</rights><rights>https://creativecommons.org/licenses/by/4.0/legalcode</rights><subject>Minimum spanning tree</subject><subject>Parallel algorithm</subject><subject>Cluster techniques</subject><title>A NEW PARALLEL ALGORITHM FOR COMPUTING MINIMUM SPANNING TREE</title><type>Journal:Article</type><type>Journal:Article</type><recordID>1283745</recordID></dc>
|
| language |
eng |
| format |
Journal:Article Journal Journal:Journal |
| author |
M. I. Moussa E. M. Badr |
| title |
A NEW PARALLEL ALGORITHM FOR COMPUTING MINIMUM SPANNING TREE |
| publishDate |
2013 |
| topic |
Minimum spanning tree Parallel algorithm Cluster techniques |
| url |
https://zenodo.org/record/1283745 |
| contents |
Computing the minimum spanning tree of the graph is one of the fundamental computational problems. In this paper, we present a new parallel algorithm for computing the minimum spanning tree of an undirected weighted graph with vertices and edges. This algorithm uses the cluster techniques to reduce the number of processors by fraction and the parallel work by the fraction O ( 1 lo g ( f ( n )) ),where f (n) is an arbitrary function. In the case f (n) =1, the algorithm runs in logarithmic-time and use super linear work on EREWPRAM model. In general, the proposed algorithm is the simplest one. |
| id |
IOS16997.1283745 |
| institution |
ZAIN Publications |
| institution_id |
7213 |
| institution_type |
library:special library |
| library |
Cognizance Journal of Multidisciplinary Studies |
| library_id |
5267 |
| collection |
Cognizance Journal of Multidisciplinary Studies |
| repository_id |
16997 |
| subject_area |
Multidisciplinary |
| city |
Stockholm |
| province |
INTERNASIONAL |
| shared_to_ipusnas_str |
1 |
| repoId |
IOS16997 |
| first_indexed |
2022-06-06T02:49:39Z |
| last_indexed |
2022-06-06T02:49:39Z |
| recordtype |
dc |
| _version_ |
1734896224830488576 |
| score |
17.538404 |