지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2012.7
- 수록면
- 87 - 95 (9page)
이용수
초록· 키워드
오류제보하기
본 논문에서는 3차원 공간상에 존재하는 많은 입력노드를 신속하게 연결하는 PTAS 3차원 스타이너 최소트리를 제안한다. 스타이너 최소트리문제는 비 다항 적 문제 영역에 속하며 적절한 휴리스틱을 도입했을 경우 다항 적 문제 영역에서 최단 길이의 해를 생성하는 최소신장트리 방법과 같은 여러 방법에 비해 우수한 성능을 보이나, 입력노드의 수가 클 경우 과도한 실행시간을 요구한다. 본 논문에서는 이 문제를 해결하기 위해 PTAS 기법을 도입한 방법을 제안한다. 3차원 공간상에 존재하는 70,000개의 입력 노드에 대한 실험에서, 본 논문에서 제안된 8개 공간 분할 PTAS 방법은, 순수 3차원 스타이너 최소트리방법에 비해 연결 길이는 0.81% 증가했으나, 실행시간은 86.88%의 단축되었다. 이는 제안된 방법이 시간적 제약이 비교적 큰 문제에서 공간상의 많은 노드들을 신속하게 연결하는 응용에 잘 적용될 수 있음을 나타낸다.
목차
등록된 정보가 없습니다.
참고문헌 (11)
참고문헌 신청
1. [학술지(정기간행물)] - G. Xue / 2001 / Grade of Service Steiner Minimum Trees in Euclidean Plane / Algorithmica 31 : 479 ~ 500
2. [인터넷자원] - / / http://en.wikipedia.org/wiki/Polynomial-time_approxim a tion_scheme
3. [학술지(정기간행물)] - N. Halman / 2009 / A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand / Journal of Mathematics of Operations Research 34 (3) : 674 ~ 685
4. [학술지(정기간행물)] - X. Zhang / 2010 / Polynomial Time Approximation Schemes for Scheduling Problems with Time Lags / Journal of Scheduling 13 (5) : 553 ~ 559
5. [학술대회논문] - A. Das / 2010 / A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing / Proceeding of SODA '10 Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics : 390 ~ 403
2. [인터넷자원] - / / http://en.wikipedia.org/wiki/Polynomial-time_approxim a tion_scheme
3. [학술지(정기간행물)] - N. Halman / 2009 / A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand / Journal of Mathematics of Operations Research 34 (3) : 674 ~ 685
4. [학술지(정기간행물)] - X. Zhang / 2010 / Polynomial Time Approximation Schemes for Scheduling Problems with Time Lags / Journal of Scheduling 13 (5) : 553 ~ 559
5. [학술대회논문] - A. Das / 2010 / A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing / Proceeding of SODA '10 Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics : 390 ~ 403
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0