현재 위치
Home
IT마케팅 및 정책
2-간선 연결 그래프를 사용한 최소신장트리 알고리즘 제안
Proposal of Minimum Spanning Tree Algorithm using 2-Edges Connected Grap
-
- 발행기관
- 국제인공지능학회(구 한국인터넷방송통신학회) 바로가기
-
- 간행물
- 한국인터넷방송통신학회 논문지 KCI 등재 바로가기
-
- 통권
- 제14권 제4호 (2014.08)바로가기
-
- 페이지
- pp.233-241
-
- 저자
-
- 언어
- 한국어(KOR)
-
- URL
- https://www.earticle.net/Article/A229069
※ 원문제공기관과의 협약기간이 종료되어 열람이 제한될 수 있습니다.
원문정보
초록
- 영어
- This paper suggests a fast minimum spanning tree algorithm which simplify the original graph to 2-edge connected graph, and using the cycling property. Borůvka algorithm firstly gets the partial spanning tree using cycle property for one-edge connected graph that selects the only one minimum weighted edge per vertex . Additionally, that selects minimum weighted edge between partial spanning trees using cut property. Kruskal algorithm uses cut property for ascending ordered of all edges. Reverse-delete algorithm uses cycle property for descending ordered of all edges. Borůvka and Kruskal algorithms always perform times for all edges. The proposed algorithm obtains 2-edge connected graph that selects 2 minimum weighted edges for each vertex firstly. Secondly, we use cycle property for 2-edges connected graph, and stop the algorithm until For actual 10 benchmark data, The proposed algorithm can be get the minimum spanning trees. Also, this algorithm reduces 60% of the trial number than Borůvka, Kruskal and Reverse-delete algorithms.
- 한국어
- 본 논문은 원 그래프를 2-간선 연결 그래프로 단순화하고, 사이클 속성을 적용하여 최소신장트리를 빠르게 얻는 알고리즘을 제안하였다. Borůvka 알고리즘은 정점 당 최소 가중치 간선 을 1개씩 선택하는 1-간선 연결 그래프에 대해 사이클 속성을 적용하여 부분신장트리를 얻는다. 추가적으로 절단속성을 적용하여 부분신장트리를 연결하는 최소 가중치 간선을 선택한다. Kruskal 알고리즘은 그래프의 모든 간선을 대상으로 오름차순으로 절단 속성을 적용한다. 역-삭제 알고리즘은 내림차순으로 사이클 속성을 적용한다. Borůvka, Kruskal과 역-삭제 알고리즘은 모든 간선들을 대상으로 하기 때문에 항상 회 수행된다. 제안된 알고리즘은 첫 번째로, 정점 당 최소 가중치 간선을 2개씩 선택하는 2-간선 연결 그래프를 얻는다. 두 번째로, 2-간선 연결 그래프에 대해 사이클 속성을 적용하여 일 때 알고리즘을 종료시켰다. 제안된 방법들을 10개의 실제 그래프들에 적용한 결과 모두 최소신장트리를 얻는데 성공하였다. 또한, Borůvka, Kruskal과 역-삭제 알고리즘에 비해 수행 횟수를 60% 단축시켰다.
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 연구 배경
Ⅲ. 2-간선 연결 그래프 MST 알고리즘
Ⅳ. 알고리즘 적용성 평가
Ⅴ. 결론 및 향후 연구과제
References
키워드
Minimum spanning tree Cycle property Cut property 2-edges connected graph Minimum weight edge저자
간행물 정보
발행기관
-
- 발행기관명
- 국제인공지능학회(구 한국인터넷방송통신학회) [The International Association for Artificial Intelligence]
- 설립연도
- 2000
- 분야
- 공학>전자/정보통신공학
- 소개
- 인터넷방송, 인터넷 TV , 방송 통신 네트워크 및 관련 분야에 대한 국내는 물론 국제적인 학술, 기술의 진흥발전에 공헌하고 지식 정보화 사회에 기여하고자 한다.
간행물
-
- 간행물명
- 한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]
- 간기
- 격월간
- pISSN
- 2289-0238
- eISSN
- 2289-0246
- 수록기간
- 2001~2025
- 십진분류
- KDC 326 DDC 380
이 권호 내 다른 논문 / 한국인터넷방송통신학회 논문지 제14권 제4호
피인용수 : 0건 (자료제공 : 네이버학술정보)
함께 이용한 논문 이 논문을 다운로드한 분들이 이용한 다른 논문입니다.
출처 : 네이버학술정보
0개의 논문이 장바구니에 담겼습니다.