지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제41권 제3호
- 발행연도
- 2014.6
- 수록면
- 146 - 150 (5page)
이용수
초록· 키워드
오류제보하기
본 논문에서는 유향 사이클 그래프의 에지 집합으로부터 사이클을 구성하는 정점들의 순서를 재구성가능한 메쉬(RMESH)에서 찾는 문제를 고려한다. 이 문제는 순차 알고리즘으로 선형 시간에 해결되는 문제이지만 선형 시간보다 낮은 차수의 재구성가능한 메쉬 알고리즘을 고안하는 것은 정점 순서가 가지는 순차성 때문에 단순하지 않다. 평면 상의 모든 다각형은 유향 사이클 그래프에 해당하기 때문에, 이 문제에 대한 해는 다각형의 정점별 이웃 정보로부터 다각형을 구성해야 하는 문제를 해결하는데 활용될 수 있다. 기존 연구로서 n개의 에지를 가진 유향 사이클 그래프의 사이클 정점 순서를 n×n<SUP>2</SUP> RMESH에서 상수 시간에 찾는 알고리즘이 나와 있다. 본 논문에서는 n×n RMESH에서 사이클 정점 순서를 O(log<SUP>2</SUP>n) 시간에 찾는 알고리즘을 제시한다. 이 알고리즘은 기존의 결과에 비해 병렬 알고리즘의 비용을 나타내는 프로세서-시간 곱 지표를 O(n<SUP>3</SUP>)에서 O(n<SUP>2</SUP>log<SUP>2</SUP>n) 으로 개선한다.
목차
요약
Abstract
1. 서론
2. 로그 시간 병렬 알고리즘
3. 결론과 연구 과제
References
참고문헌 (9)
참고문헌 신청
1. [학술대회논문] - R. Miller / 1988 / Meshes with Reconfigurable Buses / Proc. 5th MIT Conf. on Adv. Res. in VLSI : 163 ~ 178
2. [학술지(정기간행물)] - R. Wankar / 2009 / Reconfigurable architectures and algorithms: a researh survey / I.J. of Computer Science and Applications 6 (1) : 108 ~ 123
3. [학술지(정기간행물)] - T. Pan / 2011 / The transitive closure and related algorithms of digraph on the reconfigurable architecture / Parallel Processing Letters 21 (1) : 27 ~ 43
4. [학술지(정기간행물)] - O. Bouattane / 2011 / Parallel c-means algorithm for image segmentation on a reconfigurable mesh computer / Parallel Computing 37 : 230 ~ 243
5. [학술대회논문] - S. H. Kim / 2013 / A constant time parallel algorithm for finding a vertex sequence of the directed cycle graph from the individual neighborhood information / Proc. 2013 Conf. on Information and Communication Engineering 17 (2) : 326 ~ 328
2. [학술지(정기간행물)] - R. Wankar / 2009 / Reconfigurable architectures and algorithms: a researh survey / I.J. of Computer Science and Applications 6 (1) : 108 ~ 123
3. [학술지(정기간행물)] - T. Pan / 2011 / The transitive closure and related algorithms of digraph on the reconfigurable architecture / Parallel Processing Letters 21 (1) : 27 ~ 43
4. [학술지(정기간행물)] - O. Bouattane / 2011 / Parallel c-means algorithm for image segmentation on a reconfigurable mesh computer / Parallel Computing 37 : 230 ~ 243
5. [학술대회논문] - S. H. Kim / 2013 / A constant time parallel algorithm for finding a vertex sequence of the directed cycle graph from the individual neighborhood information / Proc. 2013 Conf. on Information and Communication Engineering 17 (2) : 326 ~ 328
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2015-560-001667641