본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보처리학회논문지. The KIPS transactions. Part A. Part A v.17A no.3, 2010년, pp.159 - 166  
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

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

이상운    (강릉원주대학교 과학기술대학 멀티미디어공학과  );
  • 초록

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


    In this paper, to obtain the Minimum Spanning Tree (MST) from the graph with several nodes having the same weight, I applied both Bor $\dot{u}$ 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 $2^{nd}$ stage of Bor $\dot{u}$ vka is quite complicating. The $1^{st}$ stage of Bor $\dot{u}$ 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 $\dot{u}$ vka's $1^{st}$ 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.


  • 주제어

    최소신장트리 .   무방향성 .   상이한 가중치 .   동일 가중치 .   사이클.  

  • 참고문헌 (9)

    1. Wikipedia, http://en.wikipedia.org/wiki/Minimum_spanning_ tree 
    2. O. Boruvka, "O Jistem Problemu Minimalnim," Prace Mor. Prrodved. Spol. V Brne (Acta Societ. Natur. Moravicae), Vol. III, No.3, pp.37-58, 1926. 
    3. J. Neeetril, E. Milkova, and H. Nesetrilova, "Otakar Boruvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History)," DMATH: Discrete Mathematics, Vol.233, 2001. 
    4. R. C. Prim, "Shortest Connection Networks and Some Generalisations," Bell System Technical Journal, Vol.36, pp.1389-1401, 1957. 
    5. J. B. Kruskal, "On the Shortest Spanning Subtree and The Traveling Salesman Problem," Proceedings of the American Mathematical Society, Vol.7, pp.48-50, 1956. 
    6. J. Erickson, "CS 473G -Graduate Algorithms," Dept. of Computer Science, University of Illinois, 2005. 
    7. WWL. Chen, "Discrete Mathematics," Department of Mathematics, Division of ICS, Macquarie University, Australia, http://www. maths.mq.edu.au/~wchen/lndmfolder/ lndm.html, 2003. 
    8. C. Peiper, CS 400 -Data Structures for Non CS-Majors, http://www.cs.uiuc.edu/class/fa05/cs400/_labs/Lab12/suuri/, 2005. 
    9. Wikipedia, http://en.wikipedia.org/wiki/Kruskal_algorithm 

 저자의 다른 논문

  • 이상운 (176)

    1. 2010 "기능점수 기반 소프트웨어 공식" 정보처리학회논문지. The KIPS transactions. Part D. Part D d17 (5): 327~336    
    2. 2011 "소수계량함수" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 16 (10): 101~109    
    3. 2011 "m-진법 모듈러 지수연산" 정보처리학회논문지. The KIPS transactions. Part C Part C c18 (1): 1~6    
    4. 2011 "최대 수용량-기반 최소절단 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 16 (5): 153~162    
    5. 2011 "화랑 문제의 최소 정점 경비원 수 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 16 (6): 179~186    
    6. 2011 "정점 색칠 문제의 다항시간 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 16 (7): 85~93    
    7. 2011 "n+1 소인수분해 알고리즘" 한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication 11 (2): 107~112    
    8. 2011 "동시개발 소프트웨어 프로세스 모델" 한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication 11 (4): 147~156    
    9. 2011 "κ-페르마 소인수분해 알고리즘" 한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication 11 (4): 157~164    
    10. 2011 "방향그래프의 최소신장트리 알고리즘" 한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication 11 (5): 159~171    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기