지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2014.1
- 수록면
- 233 - 241 (9page)
이용수
초록· 키워드
오류제보하기
본 논문은 원 그래프를 2-간선 연결 그래프로 단순화하고, 사이클 속성을 적용하여 최소신장트리를 빠르게 얻는 알고리즘을 제안하였다. Bor？vka 알고리즘은 정점 (v) 당 최소 가중치 간선 (v) 을 1개씩 선택하는 1-간선 연결 그래프에 대해 사이클 속성을 적용하여 부분신장트리를 얻는다. 추가적으로 절단속성을 적용하여 부분신장트리를 연결하는 최소 가중치 간선을 선택한다. Kruskal 알고리즘은 그래프의 모든 간선을 대상으로 오름차순으로 절단 속성을 적용한다. 역-삭제 알고리즘은 내림차순으로 사이클 속성을 적용한다. Bor？vka, Kruskal과 역-삭제 알고리즘은 모든 간선들을 대상으로 하기 때문에 항상 |e| 회 수행된다. 제안된 알고리즘은 첫 번째로, 정점 당 최소 가중치 간선을 2개씩 선택하는 2-간선 연결 그래프를 얻는다. 두 번째로, 2-간선 연결 그래프에 대해 사이클 속성을 적용하여 |e|=|v|-1 일 때 알고리즘을 종료시켰다. 제안된 방법들을 10개의 실제 그래프들에 적용한 결과 모두 최소신장트리를 얻는데 성공하였다. 또한, Bor？vka, Kruskal과 역-삭제 알고리즘에 비해 수행 횟수를 60% 단축시켰다.
목차
등록된 정보가 없습니다.
참고문헌 (15)
참고문헌 신청
Wikipedia / Minimum Spanning Tree
J. Kleinberg / 2004 / Algorithm Design / Addison-Wesley
O. Borůvka / 1926 / O Jistem Problemu Minimalnim / Prace Mor. Prrodved. Spol. V Brne (Acta Societ. Natur. Moravicae) 3(3):37~58
J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History) / DMATH: Discrete Mathematics 233(1-3):3~36
R. C. Prim / 1957 / Shortest Connection Networks and Some Generalisations / Bell System Technical Journal 36(6):1389~1401
J. Kleinberg / 2004 / Algorithm Design / Addison-Wesley
O. Borůvka / 1926 / O Jistem Problemu Minimalnim / Prace Mor. Prrodved. Spol. V Brne (Acta Societ. Natur. Moravicae) 3(3):37~58
J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History) / DMATH: Discrete Mathematics 233(1-3):3~36
R. C. Prim / 1957 / Shortest Connection Networks and Some Generalisations / Bell System Technical Journal 36(6):1389~1401
이 논문의 저자 정보
최근 본 자료
댓글(0)
0