PRIM’S MINIMUM COST SPANNING TREE

Muhammad Haziq Azrin #1, Mohamed Faidz Mohamed Said #2 

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 muhdhaziq36@gmail.com
2 faidzms@ieee.org

 
Abstract—In this anticipate we will clarify about what Prim’s minimum cost spanning tree is. Prim’s algorithm is a greedy algorithm that discovers a minimum spanning tree for a weighted undirected graph. A weighted graph is a graph in which each side has a weight for several real number and is the total of the weights of all sides. Every connected graph has a spanning tree. Minimum spanning tree is a typical issue in graph theory that assumes a key part in a wide area of use and a minimum spanning tree in an undirected associated weighted diagram is a spanning tree of least weight among all spreading over trees.
Keywords: Prim’s algorithm, Weighted graph, Spanning tree, Greedy algorithm.



REFERENCES

[1]	Bergantiños, Gustavo, and María Gómez-Rúa. "An axiomatic approach in minimum cost spanning tree problems with groups." Annals of Operations Research 225.1: 45-63 J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68–73, 2015.

[2]	Bergantiños, Gustavo, and Anirban Kar. "On obligation rules for minimum cost spanning tree problems." Games and Economic Behavior 69.2: 224-237, 2010.

[3]	Dutta, Bhaskar, and Anirban Kar. "Cost monotonicity, consistency and minimum cost spanning tree games." Games and Economic Behavior 48.2: 223-248, 2004.

[4]	Hougaard, Jens Leth, Hervé Moulin, and Lars Peter Østerdal. "Decentralized pricing in minimum cost spanning trees." Economic Theory 44.2: 293-306, 2010.

[5]	Kar, Anirban. "Axiomatization of the Shapley value on minimum cost spanning tree games." Games and Economic Behavior 38.2: 265-277, 2002.

[6]	Prim, Robert Clay. "Shortest connection networks and some generalizations." Bell system technical journal 36.6: 1389-1401, 1957.

[7]	Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical society 7.1: 48-50, 1956.

[8]	Moret, Bernard ME, and Henry D. Shapiro. "An empirical assessment of algorithms for constructing a minimum spanning tree." DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science 15: 99-117, 1994

[9]	Noshita, Kohei. "A theorem on the expected complexity of Dijkstra's shortest path algorithm." Journal of Algorithms 6.3: 400-408, 1985.

[10]	Moulin, Hervé. "Welfare bounds in the cooperative production problem."Games and Economic Behavior 4.3: 373-401, 1992.

[11]	Sharkey, William W. The theory of natural monopoly. Vol. 5. Cambridge: Cambridge University Press, 1982.

[12]	Demko, Stephen, and Theodore P. Hill. "Equitable distribution of indivisible objects." Mathematical Social Sciences 16.2: 145-158, 1988.

[13]	Moulin, Hervé. "Characterizations of the pivotal mechanism." Journal of Public Economics 31.1: 53-78, 1986..

[14]	Thomson, William. "Maximin strategies and elicitation of preferences."Laffont JJ, Aggregation and revelation of preferences. North Holland, Amsterdam, 1979.