Downloads: 138 | Views: 286 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1
Research Paper | Mathematics | Iraq | Volume 4 Issue 7, July 2015 | Popularity: 6.5 / 10
An Approach for Solving Transportation Problem Using Modified Kruskal's Algorithm
Kadhim B. S. Aljanabi, Anwar Nsaif Jasim
Abstract: This paper presents a new approach for finding a minimum feasible solution for transportation problem with different types (balanced and unbalanced). The approach is based mainly on using graph theory in general and Kruskals algorithm for finding Minimum Spanning Tree (MST) in finding out the first minimum cost between sources and demands. All the edges between sources and demands are sorted in an ascending order according to the weights (costs of unit delivery between sources and demands) in an array. Starting from the first element of the array which represents the absolute minimum cost, then delete either the source vertex with all its outgoing edges if this source is satisfied or deleting the targeted demand with all its incoming edges if this demand is satisfied or even both. Different examples are considered in this paper to study the correctness and the scalability of the proposed approach. The examples cover both balanced and unbalanced transportation models. As Kruskals algorithm works with O (E log V) time complexity, where E represents the number of edges and V is the number of vertices, however, the proposed approach tends to reduce the number of vertices and the edges after each iteration and hence it will converge faster.
Keywords: Graph, Algorithms, Transportation Problem, Kruskals algorithm, MST
Edition: Volume 4 Issue 7, July 2015
Pages: 2426 - 2429
Make Sure to Disable the Pop-Up Blocker of Web Browser
Similar Articles
Downloads: 153 | Weekly Hits: ⮙1 | Monthly Hits: ⮙2
Research Paper, Mathematics, India, Volume 6 Issue 11, November 2017
Pages: 1792 - 1796A Study on Graph with Desmos through ICT in Diploma in Elementary Education of Tamil Nadu State Board
P. Charles Paul, G. Thulasi
Downloads: 132 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1
Research Paper, Mathematics, India, Volume 9 Issue 2, February 2020
Pages: 687 - 690Chromatic Number and Weak Complement of L-Fuzzy Graphs
Sreedevi V.S., Dr. Bloomy Joseph
Downloads: 0
Research Paper, Mathematics, India, Volume 11 Issue 8, August 2022
Pages: 790 - 793On Sanskruti Index of the Line Graphs of Certain Nanostructures
Dr. K Vijila Dafini, Dr. M Little Flower, Dr. X Lenin Xaviour
Downloads: 0
Masters Thesis, Mathematics, Indonesia, Volume 11 Issue 10, October 2022
Pages: 207 - 218Ethnomathematics in Balinese Dance Movements and Its Potential for Learning
Luh Dewi, Sariyasa, Gede Suweken
Downloads: 0
Research Paper, Mathematics, India, Volume 12 Issue 4, April 2023
Pages: 1892 - 1896Neighbour Degree Connectivity Indices of Graphs and Its Applications to the Octane Isomers
Ashwini Yalaniak, Supriya Butte