Earticle

초록

영어

The art gallery problem(AGP) is the problem of obtaining the minimum number of guards who can monitor the entire gallery(wall, vertex, and inner space) inside the polygon. AGP is known as NP-hard, where an algorithm for finding an exact solution in polynomial time is not known. The three-graph coloring method(TGC) of triangles widely known for LL ≤ g(P) ≤ UL can obtain an upper limit of g(P) ≤ ⌊ n/3 ⌋ for n vertices. On the other hand, independent dominating set(IDS) algorithms may perform better than TGCs, while they may not cover some line segment. In this paper, a connected dominating set(CDS) algorithm is proposed as a method of obtaining a smaller number of guards than TGC or IDS while covering the entire interior of the art gallery. Experiments on eight problems showed that CDS showed the best performance.

한국어

화랑문제는 다각형 내부의 화랑 전체(벽, 꼭짓점, 내부 공간)를 감시할 수 있는 최소 경비원 수를 구하는 문제이다. 화랑문제는 다항시간으로 정확한 해를 찾는 알고리즘이 알려져 있지 않은 NP-난제(NP-hard)로 알려져 있다. LL ≤ g(P) ≤ UL에 대해 널리 알려진 삼각형의 3색 색칠 법(TGC)은 n개 꼭짓점에 대해 g(P) ≤ ⌊ n/3 ⌋인 상한치 (upper limit)을 구할 수 있다. 반면에 독립 지배집합(IDS) 알고리즘은 TGC보다 성능이 좋은 반면에 일부 변을 커버하 지 못하는 경우가 발생할 수 있다. 본 논문에서는 화랑 내부 전체를 커버하면서도 TGC나 IDS에 비해 보다 적은 수의 경비원 수를 구하는 방법으로 연결 지배집합(CDS) 알고리즘을 제안하였다. 8개 문제에 대해 실험 결과 CDS가 가장 우수한 성능을 보였다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 문제점
Ⅲ. 연결 지배집합 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 교수 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380