International Journal of System & Software Engineering

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

An Optimisation Approach for Construction of a Distributed Minimum Spanning Tree (DMST) Using MPI


Affiliations
1 Department of CSE, Pabna University of Science and Technology, Pabna, Bangladesh
     

   Subscribe/Renew Journal


The present paper determines Distributed Minimum Spanning Tree (DMST) of very large graphs. It is very time consuming to calculate in a single machine. So the researcher has used parallel programming. One of the DMST algorithms that support parallel computing is Boruvka's algorithm. The researcher has used this algorithm. To avail the parallelism, we have used the MPI architecture.

Keywords

Distributed Minimum Spanning Tree (DMST), Message Passing Interface (MPI), Parallelism, Boruvka’s Algorithm.
Subscription Login to verify subscription
User
Notifications
Font Size


  • Bergantinos, G., & Lorenzo, L. (2008). Non cooperative cost spanning tree problems with budget restrictions. Naval Research Logistics, 55(8), 747-757.

  • Bergantinos, G., & Lorenzo-Freire, S. (2008). Optimistic weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research, 185(1), 289-298.

  • Bergantinos, G., & Vidal-Puga, J. (2007). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137(1), 326-352.

  • Bergantinos, G., & Vidal-Puga, J. (2009). Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics, 45(1), 38-42.

  • Bird, C. G. (1976). On cost allocation for a spanning tree. A game theoretic approach Networks, 6, 335-350.

  • Bogomolnaia, A., Holzman, R., & Moulin, H. (2008). Sharing the cost of a capacity network. Mimeo Rice University. Retrieved from http://www.ruf.rice.edu/˜econ/faculty/moulin.html.

  • Bogomolnaia, A., & Moulin, H. (2008). Sharing the cost of a minimal cost spanning tree: Beyond the folk solution. Mimeo. Rice University. Retrieved from http://www.ruf.rice.edu/˜econ/faculty/moulin.html.

  • Boruvka, O., & Jistem, J. (1926). About a certain minimal problem. Praca Moravske Prirodovedecke Spolecnosti, 3, 37-58.

  • Branzei, R., Moretti, S., Norde, H., & Tijs, S. (2004). The P-value for cost sharing in minimum cost spanning tree situations. Theory and Decision, 56(1), 47-61.

  • Dutta, B., & Kar, A. (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior, 48 (2), 223-248.

  • Feltkamp, V., Tijs, S., & Muto, S. (1994). On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo (1994a), Tilburg University. Retrieved from http://arno.uvt.nl/show.cgi?fid=3002

  • Kruskal, L. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48-50.

  • Norde, H., Moretti, S., & Tijs, S. (2004). Minimum cost spanning tree games and population monotonic allocation schemes. European Journal of Operational Research, 154(1), 84-97.

  • Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell Systems Technology Journal, 36(6), 1389-1401.

  • http://books.google.com.bd/books

  • http://en.wikipedia.org/wiki/Distributed_minimum_spanning_tree

  • http://www.cs.princeton.edu/courses/archive/spring13/cos423/ lectures/04DemoBoruvka.pdf

  • Barr, R. S. (1989). Minimal spanning trees: An empirical investigation of parallel algorithms. Parallel Computing, 12(1), 45-52.


Abstract Views: 293

PDF Views: 0




  • An Optimisation Approach for Construction of a Distributed Minimum Spanning Tree (DMST) Using MPI

Abstract Views: 293  |  PDF Views: 0

Authors

Md. Akkas Ali
Department of CSE, Pabna University of Science and Technology, Pabna, Bangladesh

Abstract


The present paper determines Distributed Minimum Spanning Tree (DMST) of very large graphs. It is very time consuming to calculate in a single machine. So the researcher has used parallel programming. One of the DMST algorithms that support parallel computing is Boruvka's algorithm. The researcher has used this algorithm. To avail the parallelism, we have used the MPI architecture.

Keywords


Distributed Minimum Spanning Tree (DMST), Message Passing Interface (MPI), Parallelism, Boruvka’s Algorithm.

References