지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2013.1
- 수록면
- 103 - 114 (12page)
이용수
초록· 키워드
오류제보하기
본 논문은 최소신장트리를 구하는 Kruskal과 역-삭제 알고리즘의 수행 횟수를 줄이는 방법을 제안하였다. 기존의 Kruskal과 역-삭제 알고리즘은 그래프의 모든 간선들을 대상으로 사이클이 발생하는지 여부를 검증한다. 이로 인해 알고리즘 수행 과정에서 이미 최소신장트리를 얻었음에도 불구하고 나머지 간선들에 대해 알고리즘을 추가로 불필요하게 수행하는 문제점을 갖고 있다. 본 논문은 먼저, Kruskal과 역-삭제 알고리즘과 동일하게 모든 간선들을 대상으로 알고리즘은 수행하지만 알고리즘 종료 시점 기준을 적용하여 수행 횟수를 줄이는 "제1방법"을 제안하였다. 다음으로, 최소신장트리에 전혀 영향을 미치지 않는 불필요한 간선을 사전에 제거하고 남은 간선들을 대상으로 최소신장트리를 찾는 "제2방법"을 제안하였다. 제안된 방법들을 실제 그래프들에 적용한 결과 기존의 Kruskal과 역-삭제 알고리즘보다 최소 1.4배에서 최대 3.86배 빨리 알고리즘을 종료시키는 효과를 얻었다. 제안된 2개 방법을 2개 알고리즘에 적용한 4개 알고리즘 중에서 역-삭제 알고리즘 "제2방법"이 가장 빨리 알고리즘을 종료시키는 결과를 얻었다.
목차
등록된 정보가 없습니다.
참고문헌 (14)
참고문헌 신청
Wikipedia / Minimum Spanning Tree
O. Borůvka / 1929 / O Jistem Problemu Minimalnim / Pra ce Mor. Prrodved. Spol. V Brne (Acta Societ. Natu r. Moravicae) Ⅲ(3):37~58
J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Tr anslation of the both 1926 Papers, Comments, Hist ory) / DMATH: Discrete Mathematics 233
R. C. Prim / 1957 / Shortest Connection Networks and So me Generalisations / Bell System Technical Journal 36:1389~1401
J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedin gs of the American Mathematical Society 7:48~50
O. Borůvka / 1929 / O Jistem Problemu Minimalnim / Pra ce Mor. Prrodved. Spol. V Brne (Acta Societ. Natu r. Moravicae) Ⅲ(3):37~58
J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Tr anslation of the both 1926 Papers, Comments, Hist ory) / DMATH: Discrete Mathematics 233
R. C. Prim / 1957 / Shortest Connection Networks and So me Generalisations / Bell System Technical Journal 36:1389~1401
J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedin gs of the American Mathematical Society 7:48~50
이 논문의 저자 정보
최근 본 자료
댓글(0)
0