간선 모집단 규모축소 기법을 적용한 빠른 최소신장트리 결정 = Fast Determination of Minimum Spanning Tree Based on Down-sizing Technique of Edges Population

다국어 초록 (Multilingual Abstract)

This paper suggests a method of lessening number of a graph's edges population in order to rapidly obtain the minimum spanning tree. The present minimum spanning tree algorithm works on all the edges of the graph. However, the suggested algorithm reduces the edges population size by means of applying a method of deleting maximum weight edges in advance from vertices with more than 2 valencies. Next, it applies a stopping criterion which ideally terminates Borůvka, Prim, Kruskal and Reverse-Delete algorithms for reduced edges population. On applying the suggested algorithm to 9 graphs, it was able to minimize averagely 83% of the edges that do not become MST. In addition, comparing to the original graph, edges are turned out to be lessened 38% by Borůvka, 37% by Prim, 39% by Kruskal and 73% by Reverse-Delete algorithm, and thereby the minimum spanning tree is obtained promptly.

참고문헌 (Reference)

1 최명복, "방향 그래프의 Prim 최소신장트리 알고리즘" 한국인터넷방송통신학회 12 (12): 51-61, 2012

2 이용진, "WSN의 최소비용 신장트리 문제와 휴리스틱 알고리즘" 한국정보기술학회 7 (7): 275-282, 2009

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

4 Wikipedia, "Reverse-Delete Algorithm" Wikimedia Foundation, Inc.

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

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

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

8 Wikipedia, "Minimum Spanning Tree" Wikimedia Foundation, Inc.

9 Wikipedia, "Graph(mathematics)" Wikimedia Foundation, Inc.