:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.25 No.2 | (2025) pp.95~102
화랑 문제에 관한 연결 지배집합 알고리즘
Abstract
화랑문제는 다각형 내부의 화랑 전체(벽, 꼭짓점, 내부 공간)를 감시할 수 있는 최소 경비원 수를 구하는 문제이다. 화랑문제는 다항시간으로 정확한 해를 찾는 알고리즘이 알려져 있지 않은 NP-난제(NP-hard)로 알려져 있다. LL ≤ g(P) ≤ UL에 대해 널리 알려진 삼각형의 3색 색칠 법(TGC)은 n개 꼭짓점에 대해 g(P) ≤ ⌊ n/3 ⌋인 상한치 (upper limit)을 구할 수 있다. 반면에 독립 지배집합(IDS) 알고리즘은 TGC보다 성능이 좋은 반면에 일부 변을 커버하 지 못하는 경우가 발생할 수 있다. 본 논문에서는 화랑 내부 전체를 커버하면서도 TGC나 IDS에 비해 보다 적은 수의 경비원 수를 구하는 방법으로 연결 지배집합(CDS) 알고리즘을 제안하였다. 8개 문제에 대해 실험 결과 CDS가 가장 우수한 성능을 보였다.
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.
Art gallery problem,Graph coloring,Independent dominating set,Connected dominating set,Overlapped cover
