지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2014.1
- 수록면
- 51 - 59 (9page)
이용수
초록· 키워드
오류제보하기
논문은 최소신장트리를 보다 빠르게 구하기 위해 그래프의 간선 모집단을 축소시키는 방법을 제안하였다. 기존의 최소신장트리 알고리즘은 그래프의 모든 간선을 대상으로 한다. 반면에, 제안된 알고리즘은 사전에 결합가가 3 이상인 정점에 대해 최대 가중치 간선을 삭제하는 방법을 적용하여 간선 모집단 크기를 축소시킨다. 다음으로 축소된 간선 모집단을 대상으로 Bor？vka, Prim, Kruskal과 역-삭제 알고리즘을 최적으로 종료시키는 종료시점 기준을 적용하였다. 9개 그래프에 제안된 알고리즘을 적용한 결과 MST에 기여를 하지 못하는 간선을 사전에 평균 38% 축소시킬 수 있었다. 또한, 원래의 그래프를 대상으로 하는 경우와 비교 결과 알고리즘에서 비교되는 간선의 수를 Bor？vka는 38%, Prim은 37%, Kruskal은 39%, 역-삭제 알고리즘은 73%를 단축시켜 신속하게 최소신장트리를 구하였다.
목차
등록된 정보가 없습니다.
참고문헌 (9)
참고문헌 신청
Wikipedia / Minimum Spanning Tree
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) / Discrete Mathematics 233
R. C. Prim / 1957 / Shortest Connection Networks and Some Generalisations / Bell System Technical Journal 36:1389~1401
J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedings of the American Mathematical Society 7:48~50
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) / Discrete Mathematics 233
R. C. Prim / 1957 / Shortest Connection Networks and Some Generalisations / Bell System Technical Journal 36:1389~1401
J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedings of the American Mathematical Society 7:48~50
이 논문의 저자 정보
최근 본 자료
댓글(0)
0