Vol. 25 No.2 | pp.95-102.

Connected Dominating Set Algorithm for Art Gallery Problem

Abstract 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 nu...
1|2|3|4
Copyright © The Institute of Internet, Broadcasting and Communication. All rights reserved.
Address : 610 Dongbu Sunville, #99-6 GaRak-dong, SongPa-gu, Seoul, Korea | Tel : +82-2-407-7718, +82-70-7404-7718, Fax : + 82-2-407-7716 E-mail: iibc@iibc.kr