Kruskal과 역-삭제 최소신장트리 알고리즘의 효율적 구현 방법

국문 초록 (Abstract)

본 논문은 최소신장트리를 구하는 Kruskal과 역-삭제 알고리즘의 수행 횟수를 줄이는 방법을 제안하였다. 기 존의 Kruskal과 역-삭제 알고리즘은 그래프의 모든 간선들을 대상으로 사이클이 발생하는지 여부를 검증한다. 이로 인해 알고리즘 수행 과정에서 이미 최소신장트리를 얻었음에도 불구하고 나머지 간선들에 대해 알고리즘을 추가로 불필요하게 수행하는 문제점을 갖고 있다. 본 논문은 먼저, Kruskal과 역-삭제 알고리즘과 동일하게 모든 간선들을 대 상으로 알고리즘은 수행하지만 알고리즘 종료 시점 기준을 적용하여 수행 횟수를 줄이는 “제1방법”을 제안하였다. 다 음으로, 최소신장트리에 전혀 영향을 미치지 않는 불필요한 간선을 사전에 제거하고 남은 간선들을 대상으로 최소신 장트리를 찾는 “제2방법”을 제안하였다. 제안된 방법들을 실제 그래프들에 적용한 결과 기존의 Kruskal과 역-삭제 알 고리즘보다 최소 1.4배에서 최대 3.86배 빨리 알고리즘을 종료시키는 효과를 얻었다. 제안된 2개 방법을 2개 알고리 즘에 적용한 4개 알고리즘 중에서 역-삭제 알고리즘 “제2방법”이 가장 빨리 알고리즘을 종료시키는 결과를 얻었다.

다국어 초록 (Multilingual Abstract)

This paper suggests a method to reduce the number of performances of Kruskal and Reverse-delete algorithms. Present Kruskal and Reverse-delete algorithms verify whether the cycle occurs within the edges of the graph. For this reason, they have problems of unnecessarily performing extra algorithms from the edges, even though they've already obtained the minimum spanning tree. This paper, first of all, suggests the 1st method which reduces the no. of performances by introducing stop point criteria of algorithm, but at the same time, performs algorithms from all the edges, just like how Kruskal and Reverse-delete algorithms. Next, it suggests the 2nd method which finds the minimum spanning tree from the remaining edges after getting rid of all the unnecessary edges which are considered not to affect the minimum spanning tree. These suggested methods have an effect of terminating algorithm at least 1.4 times and at most 3.86times than Kruskal and Reverse-delete algorithms, when applied to the real graphs. We have found that the 2nd method of the Reverse-delete algorithm has the fastest speed in terminating an algorithm, among 4 algorithms which are results of the 2 suggested methods being applied to 2 algorithms.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련 연구와 연구 배경
• 1. Kruskal과 역-삭제 MST 알고리즘
• 2. 알고리즘 적용 문제점과 연구 배경
• Ⅲ. Kruskal과 역-삭제 MST 알고리즘의 효율적 구현 방법
• 1. 제안 알고리즘
• 2. 제1방법 적용
• 3. 제2방법 적용
• Ⅳ. 알고리즘 적용성 평가
• 1. 알고리즘 적용
• 2. 적용 결과 분석
• Ⅴ. 결론
• 참고문헌

참고문헌 (Reference)

1 박형근, "유비쿼터스 센서 네트워크를 위한 트리 라우팅 구조의 임베디드 시스템 구현" 한국산학기술학회 12 (12): 4531-4535, 2011

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

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

4 Wikipedia, "Reverse-Delete Algorithm" Wiki media Foundation, Inc.

5 Wikipedia, "Prim's Algorithm" Wikimedia Foundation, Inc.

6 J. Nešetřil, "Otakar Borůvka on Minimum Spanning Tree Problem (Tr anslation of the both 1926 Papers, Comments, Hist ory)" 233 : 2001

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

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

9 Wikipedia, "Minimum Spanning Tree"

10 Wikipedia, "Graph (mathematics)" Wikimedia Fo undation, Inc.

11 Wikipedia, "Glossary of Graph Theory" Wikimedia Foundation, Inc

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

13 C. Peiper, "CS 400 - Data Structures for Non CSMajors"

14 왕위준, "Bond Graph Modeling, Analysis and Control of Dual Stage System" 한국산학기술학회 13 (13): 1453-1459, 2012