Research Article
MINIMUM SPANNING TREE ALGORITHM
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 1 - Issue 8 |
| Published: February 2010 |
| Authors: Vikas.C.S |
10.5120/185-321
|
Vikas.C.S . MINIMUM SPANNING TREE ALGORITHM. International Journal of Computer Applications. 1, 8 (February 2010), 38-44. DOI=10.5120/185-321
@article{ 10.5120/185-321,
author = { Vikas.C.S },
title = { MINIMUM SPANNING TREE ALGORITHM },
journal = { International Journal of Computer Applications },
year = { 2010 },
volume = { 1 },
number = { 8 },
pages = { 38-44 },
doi = { 10.5120/185-321 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2010
%A Vikas.C.S
%T MINIMUM SPANNING TREE ALGORITHM%T
%J International Journal of Computer Applications
%V 1
%N 8
%P 38-44
%R 10.5120/185-321
%I Foundation of Computer Science (FCS), NY, USA
Abstract
An algorithm for minimum spanning tree[1] is discussed here. Apart from the traditional Kruskal's[2] and Prim's[3] algorithm for finding the minimum spanning tree, yet another algorithm for the same purpose is described here. Initially we form a forest and then we convert the forest into the minimum spanning tree.
References
- Thomas.H.Corman, Charles.E.Leisserson, Ronald.L.Rivest & Clifford Stein, "Introduction To Algorithms" Second Edition, Page 561.
- Thomas.H.Corman, Charles.E.Leisserson, Ronald.L.Rivest & Clifford Stein, "Introduction To Algorithms" Second Edition, Page 567.
- Thomas.H.Corman, Charles.E.Leisserson, Ronald.L.Rivest & Clifford Stein, "Introduction To Algorithms" Second Edition, Page 577.
- http://en.wikipedia.org/wiki/Greedy_algorithm
- http://en.wikipedia.org/wiki/Travelling_salesman_problem
- http://en.wikipedia.org/wiki/Kruskal's_algorithm
- http://en.wikipedia.org/wiki/Prim%27s_algorithm
Index Terms
Keywords