하이브리드 최소신장트리 알고리즘 = Hybrid Minimum Spanning Tree Algorithm

다국어 초록 (Multilingual Abstract)

In this paper, to obtain the Minimum Spanning Tree (MST) from the graph with several nodes having the same weight, I applied both Borůvka and Kruskal MST algorithms. The result came out to such a way that Kruskal MST algorithm succeeded to obtain MST, but not did the Prim MST algorithm. It is also found that an algorithm that chooses Inter-MSF MWE in the 2nd stage of Borůvka is quite complicating. The 1st stage of Borůvka has an advantage of obtaining Minimum Spanning Forest (MSF) with the least number of the edges, and on the other hand, Kruskal MST algorithm has an advantage of always obtaining MST though it deals with all the edges. Therefore, this paper suggests an Hybrid MST algorithm which consists of the merits of both Borůvka's 1st stage and Kruskal MST algorithm. When applied additionally to 6 graphs, Hybrid MST algorithm has a same effect as that of Kruskal MST algorithm. Also, comparing the algorithm performance speed and capacity, Hybrid MST algorithm has shown the greatest performance Therefore, the suggested algorithm can be used as the generalized MST algorithm.

국문 초록 (Abstract)

본 논문에서는 여러 간선들이 동일한 가중치를 갖고 있는 그래프에서 최소신장트리 (Minimum Spanning Tree, MST)를 얻기 위해 Borůvka, Prim과 Kruskal MST 알고리즘을 실제 그래프에 적용한 결과 Borůvka와 Kruskal MST 알고리즘은 MST를 얻었지만 Prim MST 알고리즘은 MST를 얻는데 실패함을 보였다. 또한, Borůvka의 2nd Stage에서 Inter-MSF MWE를 선택하는 알고리즘이 복잡함을 알 수 있었다. Borůvka의 1st Stage는 최소한의 간선들로 최소신장 포레스트 (Minimum Spanning Forest, MSF)를 얻는 장점을 갖고 있으며, Kruskal MST 알고리즘은 모든 간선들을 대상으로 하지만 항상 MST를 얻는 장점을 갖고 있다. 따라서 본 논문은 Borůvka의 1st Stage와 Kruskal MST 알고리즘의 장점을 결합한 하이브리드 MST 알고리즘을 제안하였다. 하이브리드 MST 알고리즘을 추가적으로 6개의 그래프에 적용한 결과 Kruskal MST 알고리즘과 동일하게 항상 MST를 얻음을 검증하였다. 또한, 알고리즘 수행속도와 메모리 용량 측면에서 비교한 결과 하이브리드 MST 알고리즘이 가장 좋은 성능을 보였다. 따라서 제안된 알고리즘을 일반화된 MST 알고리즘으로 채택이 가능할 것이다.

참고문헌 (Reference)

1 Wikipedia, "http://en.wikipedia.org/wiki/Minimum_spanning_ tree"

2 Wikipedia, "http://en.wikipedia.org/wiki/Kruskal_algorithm"

3 R.C.Prim, "Shortest Connection Networks and Some Generalisations" 36 : 1389-1401, 1957

4 J. Nešetřil, "Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History)" 223 : 2001

5 J.B.Kruskal, "On the Shortest Spanning Subtree and The Traveling Salesman Problem" 48-50, 1956

6 O. Borůvka, "O Jistem Problemu Minimalnim" Ⅲ (Ⅲ): 37-58, 1926

7 WWL. Chen, "Discrete Mathematics" Department of Mathematics, Division of ICS, Macquarie University

8 J.Erickson, "CS 473G - Graduate Algorithms" University of Illinois 2005

9 C. Peiper, "CS 400 - Data Structures for Non CS-Majors"