Open Access
Subscription Access
Open Access
Subscription Access
An Optimisation Approach for Construction of a Distributed Minimum Spanning Tree (DMST) Using MPI
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
Font Size
Information
- 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: 383
PDF Views: 0