지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2011.6
- 수록면
- 179 - 186 (8page)
이용수
초록· 키워드
오류제보하기
본 논문은 화랑 문제의 최소 정점 경비원 수를 구하는 알고리즘을 제안하였다. n개의 사각형 방으로 구성된 화랑의 최소 경비원수는 정확한 해를 구하는 공식이 제안되었다. 그러나 단순하거나 장애물이 있는 다각형 또는 직각 다각형에 대해 최대 경비원수를 구하는 공식만이 제안되었으며, 최소 경비원수를 구하는 근사 알고리즘만이 제안되고 있다. n개의 정점으로 구성된 다각형 P에 대한 최대 정점 경비원 수를 구하는 방법은 Fisk가 다음과 같이 제안하였다. 첫 번째로, n-2개의 삼각형으로 구성된 삼각분할을 수행한다. 두 번째로 3색-정점색칠을 한다. 세 번째로 최소 원소를 가진 채색수를 정점 경비원의 위치로 결정한다. 본 논문에서는 지배집합으로 최소 정점 경비원 수를 구한다. 첫 번째로, 가능한 모든 가시적인 정점들 간에 간선을 그린 가시성 그래프를 얻는다. 두 번째로, 가시성그래프로부터 직접 지배집합을 얻는 방법과 가시성 행렬로부터 지배집합을 얻는 방법을 적용하였다. 다양한 화랑 문제에 적용한 결과 제안된 알고리즘은 단순하면서도 최소 정점 경비원 수를 얻을 수 있었다.
목차
등록된 정보가 없습니다.
참고문헌 (12)
참고문헌 신청
1. [인터넷자원] - Wikipedia / / Art Gallery Problem
2. [인터넷자원] - J.Barrow / / The Maths of Pylons, Art Galleries and Prisons Under the Spotlight
3. [인터넷자원] - S. K. Ghosh / / Art Gallery Theorems and Approximation Algorithms
4. [인터넷자원] - J. Urrutia / / Art Gallery and Illumination Problems
5. [학술지(정기간행물)] - T. C. Shermer / 1992 / Recent Results in Art Galleries / Proceedings of the IEEE 80 (9)
2. [인터넷자원] - J.Barrow / / The Maths of Pylons, Art Galleries and Prisons Under the Spotlight
3. [인터넷자원] - S. K. Ghosh / / Art Gallery Theorems and Approximation Algorithms
4. [인터넷자원] - J. Urrutia / / Art Gallery and Illumination Problems
5. [학술지(정기간행물)] - T. C. Shermer / 1992 / Recent Results in Art Galleries / Proceedings of the IEEE 80 (9)
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0