earticle

논문검색

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

원문정보

An Efficient Implementation of Kruskal's and Reverse-Delete Minimum Spanning Tree Algorithm

최명복, 이상운

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

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.

한국어

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

목차

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

저자정보

  • 최명복 Myeong-Bok Choi. 종신회원, 강릉원주대학교 멀티미디어공학과
  • 이상운 Sang-Un Lee. 정회원, 강릉원주대학교, 멀티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,300원

      0개의 논문이 장바구니에 담겼습니다.