지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2012.1
- 수록면
- 63 - 69 (7page)
이용수
초록· 키워드
오류제보하기
n개의 정점으로 구성된 화랑 P에 대한 최대 이동 경비원 수는 단순 다각형은 ${\lfloor}n/4{\rfloor}$, 직각 다각형은 ${\lfloor}(3n+4)/16{\rfloor}$이며, 최소 경비원수를 구하는 다항시간 알고리즘은 알려져 있지 않아 NP-난제 (NP-Hard)이다 . 본 논문은 화랑 문제의 최소 이동 경비원 수를 구하는 다항시간 알고리즘을 제안하였다. 첫 번째로, 모든 정점에서 볼 수 있는 다른 정점으로 간선을 그린 가시성 그래프를 얻는다. 두 번째로 ${\Delta}(G)$인 정점 u와 $N_G(u)$에 있는 ${\Delta}(G)$ 정점 v를 선택하고 가시성 간선과 부속 간선을 삭제한다. 세 번째로, 남아 있는 부분 그래프 각각에 대해 정점 $w_i$를 선택하여 이동 경비원이 위치할 간선을 선택하였다. 제안된 알고리즘을 다양한 단순 다각형과 직각 다각형 화랑 문제에 적용한 결과 선형시간으로 최소 이동 경비원 수를 얻었다.
목차
등록된 정보가 없습니다.
참고문헌 (15)
참고문헌 신청
Wikipedia / Art Gallery Problem
J. Barrow / The Maths of Pylons, Art Galleries and Prisons Under the Spotlight / Gresham College
S. K. Ghosh / Art Gallery Theorems and Approximation Algorithms / School of Technology & Computer Science, Teta Institute of Fundamental Research
J. Urrutia / 1996 / Art Gallery and Illumination Problems, In Handbook of Computational Geometry / Department of Computer Science, University of Ottawa
I. Bjorlings-Sachs / 1998 / Edge Guards in Rectilinear Polygons / Computational Geometry 11:111~123
J. Barrow / The Maths of Pylons, Art Galleries and Prisons Under the Spotlight / Gresham College
S. K. Ghosh / Art Gallery Theorems and Approximation Algorithms / School of Technology & Computer Science, Teta Institute of Fundamental Research
J. Urrutia / 1996 / Art Gallery and Illumination Problems, In Handbook of Computational Geometry / Department of Computer Science, University of Ottawa
I. Bjorlings-Sachs / 1998 / Edge Guards in Rectilinear Polygons / Computational Geometry 11:111~123
이 논문의 저자 정보
최근 본 자료
댓글(0)
0