Abstract
本篇論文提出並解決三個新的格點型博物館(gallery) 上的守衛問題(guarding pro-blem )：最小獨立守衛集問題(the minimum independent guarding set problem)，最小d 聯防守衛集問題(the minimum d-connected guarding set problem)和最小全聯守衛集問題(the minimum all-connected guarding set problem)。對於最小全聯防守衛集問題本篇論文給出一個時間複雜度為多項式函數(polynomial time comple-xity) 的演算法 (algorithm)，對於另兩個問題則證明它們是 NP-hard，並且分別描述了兩個估計演算法 (approximation algorithm)以及導出這兩個估計演算法的最大可能誤差 (bound)。一個格點型博物館是由數條兩兩交叉的水平和垂直走道所組成。在某些交叉點上放有一些展覽中的鑽石。為了避免這些鑽石失竊，我們必須安排一此警衛去看守它們。每個警衛都會被安排在交叉口上，以看守一條垂直走道和一條水平走道上的所有鑽石。問題是：要如果安排最少的警衛來看守到所有的鑽石。又考慮警衛可能受歹徒襲擊，因此安排警衛時，最好使他們彼此聯防。最小獨立守衛信問題就是：如何去安排最少個數的警衛來看守所有的鑽石，而且警衛間彼此不可聯防。最小 d聯防守衛集問題就是：如何去安排最少個數的警衛來看守所有的鑽石，而且每個警衛至少要和其他 d-1個警衛聯防。最小全聯防守衛集問題就是：如何去安排最少個數的警衛來看守所有的鑽石，而且所有的警衛都要彼此聯防。由於格點型博物館和二分圖形(bipartite graph) 間有很密切的關係，所以本論文中引用了許多二分圖形的配對理論(matching theory) 和覆蓋問題(covering problem)的性質。本論文的貢獻則在於提出一種新的問題，並且得到它們在演算法上的重要性質。