지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2011.2
- 수록면
- 6 - 13 (8page)
이용수
초록· 키워드
오류제보하기
본 논문은 ad hoc 네트워크 또는 센서 네트워크상에서, 주어진 노드들 사이를 상호연결하기 위해 중간노드들을 추가 배치시키는 형태의 상호연결 문제에 대한 연구이다. 이 문제는 NP hard problem으로 변환된다. 네트워크의 노드들은 응용시스템 또는 지형적인 요인에 의해 일부지역에서는 밀집하여 분포되고, 그 외의 지역에서는 희박하게 분포될 수 있다. 이러한 경우, 노드들이 밀집한 지역의 상호연결을 무시함으로써, 보다 짧은 실행시간 안에 추가노드들의 최적배치에 근접하도록 하는 방법을 만들 수 있다. 그러나 이러한 경우라 하더라도 여전히 NP hard이므로, 동적프로그래밍을 구현함으로써 다항시간 근사전략(PTAS)을 구성하는 것이 타당하다. 실행결과 등에 대한 분석은 목적함수를 적절하게 정의함으로써 가능해 진다. 목적함수는 노드 밀집지역을 추상화시킴에 의해 발생하게 되는 문제점에 대처할 수 있도록 정의되어야 한다.
목차
요약
Abstract
Ⅰ. Introduction
Ⅱ. Total Length and Other Definitions
Ⅲ. Shifting into the Integer Coordinates
Ⅳ. Partitioning, Portals and the Structure Theorem
Ⅴ. The Polynomial Time Dynamic Programming (DP)
Ⅵ. Proof of the Structure Theorem
Ⅶ. Conclusion
References
저자소개
참고문헌 (8)
참고문헌 신청
E.N. Gilbert / 1968 / Steiner minimal trees / SIAM Journal on Applied Mathematics 16:1~29
X. Cheng / 2001 / A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways / Journal of Combinatorial Optimization 5(3):327~343
DING-ZHU DU / 1999 / Interconnecting Highways / SIAM Discrete Mathematics 12:252~261
Z.A. Melzak / 1961 / On the problem of Steiner / Canadian Mathematics Bulletin 4:143~148
Ding-Zhu Du / 2000 / Theory of Computational Complexity / Wiley Inter-Science
X. Cheng / 2001 / A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways / Journal of Combinatorial Optimization 5(3):327~343
DING-ZHU DU / 1999 / Interconnecting Highways / SIAM Discrete Mathematics 12:252~261
Z.A. Melzak / 1961 / On the problem of Steiner / Canadian Mathematics Bulletin 4:143~148
Ding-Zhu Du / 2000 / Theory of Computational Complexity / Wiley Inter-Science
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2012-569-004322317