지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2010.9
- 수록면
- 25 - 34 (10page)
이용수
초록· 키워드
오류제보하기
스타이너 포인트들을 추가하여 모든 입력 노드들을 최단 길이로 연결하는 스타이너 최소 트리는 최소 신장 트리에 비해 전체 길이는 짧으나, 그것을 생성하는 문제는 NP-Complete 영역에 속한다. 이 문제를 위한 휴리스틱들은, 입력 노드의 수가 매우 큰 경우에는 많은 시간과 계산을 요구한다. 본 논문에서는 많은 입력 노드에 대해, 최하위 계층에서 포탈을 이용한 모든 가능한 단위 스타이너 트리들을 생성하고 각 상위 계층에서 이들을 계층별 병합 처리하여 최상위 계층에서 최소 비용의 트리를 선택하는 효과적인 PTAS 기법을 제안한다. 16,000개의 입력 노드와 최하위 계층에서 16개의 단위 영역으로 설계된 실험에서 생성된 PTAS 스타이너 트리는, pure 스타이너 트리의 길이에 비해 길이가 0.24% 증가되었으나, 생성 시간은 직렬 처리는 85.4%, 병렬처리는 98.9% 개선되었다. 따라서 제안하는 PTAS 스타이너 트리 생성 기법은 많은 입력 노드들에 대해 근사 스타이너 트리를 신속히 생성하는 응용에 잘 적용될 수 있을 것이다.
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 본론
Ⅳ. 실험 및 분석
Ⅴ. 결론
참고문헌
저자소개
참고문헌 (12)
참고문헌 신청
1. [학술대회논문] - A. Hayrapetyan / 2005 / Network Design for Information Networks / Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms : 933 ~ 942
2. [인터넷자원] - / / http://en.wikipedia.org/wiki/Steiner_tree
3. [학술지(정기간행물)] - S.Arora / 1998 / Polynomial-time Approximation Schemes for Euclidean TSP and Other Geometric Problems / Journal of ACM 45 (5) : 753 ~ 782
4. [학술지(정기간행물)] - X. Cheng / 2001 / A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways / Journal of Combinatorial Optimization 5 (3) : 327 ~ 343
5. [학술지(정기간행물)] - 김재각 / 2009 / 원격 검침 시스템에서 근사 최소 스타이너 트리를 이용한 집중기 및 중계기의 효율적인 배치와 연결 / 한국통신학회논문지B 34 (10) : 994 ~ 1003
2. [인터넷자원] - / / http://en.wikipedia.org/wiki/Steiner_tree
3. [학술지(정기간행물)] - S.Arora / 1998 / Polynomial-time Approximation Schemes for Euclidean TSP and Other Geometric Problems / Journal of ACM 45 (5) : 753 ~ 782
4. [학술지(정기간행물)] - X. Cheng / 2001 / A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways / Journal of Combinatorial Optimization 5 (3) : 327 ~ 343
5. [학술지(정기간행물)] - 김재각 / 2009 / 원격 검침 시스템에서 근사 최소 스타이너 트리를 이용한 집중기 및 중계기의 효율적인 배치와 연결 / 한국통신학회논문지B 34 (10) : 994 ~ 1003
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
PTAS를 이용한 3차원 스타이너 최소트리의 신속한 구성
한국컴퓨터정보학회논문지
2012 .07
-
들로네 삼각망과 최소신장트리를 결합한 효율적인 유클리드 스타이너 최소트리 생성
한국컴퓨터정보학회논문지
2014 .01
-
A Comparison of Group Steiner Tree Formulations
대한산업공학회지
2011 .09
-
스타이너 트리를 구하기 위한 부동소수점 표현을 이용한 유전자 알고리즘
한국정보통신학회논문지
2004 .08
-
원격 검침 시스템에서 근사 최소 스타이너 트리를 이용한 집중기 및 중계기의 효율적인 배치와 연결
한국통신학회논문지
2009 .10
-
비 균등 노드 분포환경에서 부분 PTAS를 이용한 효과적인 유클리드 최소신장트리 생성
한국컴퓨터정보학회논문지
2014 .06
-
Grade Of Services Steiner Minimum Tree 문제에 대한 휴리스틱의 성능 개선을 위한 G-Condition 검사 방법에 대한 연구
멀티미디어학회논문지
2008 .01
-
전기공학 교육을 위한 Steiner (Fermat) Tree 강의 Note - Minimum Spanning Tree와 Steiner Tree의 길이 비교 -
조명·전기설비학회논문지
2019 .06
-
병목 스타이너 트리의 정확한 해를 찾는 알고리즘
한국정보과학회 학술발표논문집
2009 .06
-
연합 처리기를 이용한 직교선형 스타이너 트리의 병렬 알고리즘 ( A Parallel Algorithm for Rectilinear Steiner Tree Using Associative Processor )
전자공학회논문지-B
1995 .08
-
유클리디언 스타이너 문제에 대한 진화해법의 개발
대한산업공학회 춘계공동학술대회 논문집
2003 .05
-
Protein Structure Optimization Using Steiner Minimal Tree
한국소음진동공학회 학술대회논문집
2009 .11
-
Two Efficient Approximation Algorithms for the Rectilinear Steiner Tree Problem
JTC-CSCC : Joint Technical Conference on Circuits Systems, Computers and Communications
1988 .01
-
Steiner Tree 이론을 이용한 최적 우편물 운송망 구축
한국조명·전기설비학회 학술대회논문집
2007 .05
-
직사각형의 둘레에 주어진 점들에 대한 최소 갯수의 Via를 갖는 직교 Steiner 트리를 구하는 알고리즘
한국정보과학회 학술발표논문집
1989 .04
-
진화 알고리즘을 적용한 멀티캐스트 경로배정
한국정보과학회 학술발표논문집
1997 .10
-
Algorithms for Solving the Degree-Constrained Steiner Tree Problems in Networks
대한산업공학회 춘계공동학술대회 논문집
1998 .04
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2012-569-003649442