Earticle

초록

영어

This paper suggests a method that obtains the minimum spanning tree (MST) far more easily and rapidly than the present ones. The suggested algorithm, firstly, simplifies a graph by means of reducing the number of edges of the graph. To achieve this, it applies a method of eliminating the maximum weight edge if the valency of vertices of the graph is equal to or more than 3. As a result of this step, we can obtain the reduced edge population. Next, it applies a method in which the maximum weight edge is eliminated within the cycle. On applying the suggested population minimizing and maximum weight edge deletion algorithms to 9 various graphs, as many as the number of cycles of the graph is executed and MST is easily obtained. It turns out to lessen 66% of the number of cycles and obtain the MST in at least 2 and at most 8 cycles by only deleting the maximum weight edges.

한국어

본 논문은 최소신장트리를 쉽고 빠르게 구하는 방법을 제안하였다. 제안된 알고리즘은 먼저, 그래프의 가중치 간선의 수를 축소시키는 방법으로 그래프를 단순화 시켰다. 간선 수를 축소시키는 방법으로는 그래프 정점의 결합가가 3 이상인 경우, 최대 가중치 간선을 제거하는 방법을 적용하였다. 다음으로, 그래프를 단순화 시킨 축소된 모집단 간선 들을 대상으로 사이클이 발생하는 부분을 확인하여 사이클 발생 간선들 중에서 최대 가중치를 갖는 간선을 삭제하는 방법을 적용하였다. 다양한 9개 그래프에 대해 제안된 사이클 최대 가중치 간선 제거 알고리즘을 적용한 결과 그래프 의 사이클 개수만큼만 수행하여 MST를 쉽게 구하는 장점을 보였다. 모집단 축소 기법을 적용한 결과, 9개 그래프의 사이클 개수를 66%로 감소시키는 결과를 얻었으며, 최소 2개에서 최대 8개의 사이클에서의 최대 가중치 간선만 삭제 하면 MST를 얻는 효과를 얻었다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 관련 연구와 연구 배경
  1. MST 알고리즘과 적용
  2. MST 알고리즘의 문제점과 연구 배경
 Ⅲ. 사이클 최대 가중치 간선 제거 MST 알고리즘
  1. 그래프의 간선 모집단 축소
  2. 사이클 최대 가중치 간선 제거 MST 알고리즘
  3. 알고리즘 성능 분석
 Ⅳ. 알고리즘 적용성 평가
 Ⅴ. 결론
 References

키워드

저자

• 최명복 [ Myeong-Bok Choi | 종신회원, 강릉원주대학교 멀티미디어공학과 ] Corresponding Author
• 한태용 [ Tae-Yong Han | 정회원, 강릉원주대학교 여성인력개발학과 ]
• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 멀티미디어공학과 ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380