- 學位論文
區塊圖與單環圖之點搜尋問題
The Node-Searching Problem on Block Graphs and Unicyclic Graphs
摘要
由Kirousis和Papadimitriou所提出的點搜尋問題是圖形搜尋問題的一種變形。其中的搜尋動作有（1）將搜尋者放置在一個點上，和（2）將搜尋者從一個點上移走。一開始，所有的邊都是髒的，也就是說逃犯可能藏匿其中。當一個邊的兩個端點都有搜尋者守著，則說這個邊被清乾淨。當所有的邊都被清乾淨，則說整個圖被清乾淨。搜尋策略是一連串可以將整個圖清乾淨的搜尋動作。點搜尋問題的目標有兩個：一個是最少搜尋者數目，稱為搜尋數。另一個則是使用最少搜尋者的搜尋策略，稱為最佳搜尋策略。 樹是少數能在線性時間內將點搜尋問題解決的圖形之一。其中的關鍵是所謂的Parsons引理，該引理描述樹的搜尋數之遞迴性質。原始Parsons引理是針對邊搜尋問題提出。根據該引理，Megiddo等人提出通道概念，使得邊搜尋數能在線性時間內求得。後來，Ellis等人證明Parsons引理也可以套用在樹的點分隔問題，一個與點搜尋等價的問題。使用標記技巧，他們提出了一個線性時間內計算一棵樹的點分隔數之演算法。然而，該演算法仍須使用O(n log n)的時間建構一棵樹的最佳版面佈局。隨後，Peng等人使用延伸通道概念設計了一個可以在線性時間內建構出一棵樹的最佳搜尋策略。另外，Skodinis也提出一個和Peng不同的演算法在線性時間內建構出一棵樹的最佳版面佈局。 在本論文中，我們將Parsons引理推廣到一般圖的點搜尋問題。根據該遞迴性質，我們將通道概念套用在區塊圖的點搜尋問題。運用通道概念和貪婪搜尋策略，我們設計了一個在有效時間內同時計算一個區塊圖的搜尋數和建構該圖的最佳搜尋策略之演算法。因而回答了一個懸而未決的問題，那就是區塊圖的點搜尋問題是可以在有效時間內解決的。 除此之外，我們也研究單環圖的點搜尋問題，其中單環圖的樹寬度為2。Bodlaender等人曾經提出不完全k-樹，固定k>=1，的路徑寬度問題之有效時間演算法，其中路徑寬度問題是另一個和點搜尋等價的問題。他們的演算法當然可以拿來解決單環圖的點搜尋問題。但是，該演算法的時間複雜度相當大，Omega(n^{4k+3})。因此，即使是樹寬度為2的圖也需要花Omega(n^{11})時間。最近，Ellis等人對於單環圖的點分隔問題提出一個O(n log n)時間但是相當複雜的演算法。在本論文中，運用導向搜尋策略的概念，我們對於單環圖的點搜尋問題提出一個不但是線性時間並且相對簡潔的演算法。
並列摘要
The node-searching problem, introduced by Kirousis and Papadimitriou, is a variant of the graph-searching problem. The allowable search moves in the node-searching problem are as follows: (1) placing a searcher on a vertex, and (2) removing a searcher from a vertex. Initially, all edges are considered dirty, i.e., possibly hiding the fugitive. A dirty edge is cleared if both its endpoints are simultaneously guarded by searchers. The entire graph is cleared, i.e., successfully searched, if all its edges are cleared. A search strategy is a sequence of search moves that will clear a graph with all edges dirty. There are two subjects in the node-searching problem on a graph G. One is to compute the search number of G, denoted by ns(G), which is the minimum number of searchers needed to clear G. The other is to construct an optimal search strategy for G, which clears G using ns(G) searchers. The class of trees is one of the few classes of graphs on which the node-searching problem can be solved in linear time. The key idea is the so-called Parsons' Lemma, the recursive characterization for the search number of a tree. Originally, Parsons' Lemma was proposed for the edge-searching problem, and based on the lemma, Megiddo et al. proposed the concept of avenue for computing the edge-search number of a tree in linear time. Later, Ellis et al. showed that Parsons' Lemma can also be applied to the vertex separation problem, a problem equivalent to the node-searching problem, on trees. Using the labelling technique, a linear-time algorithm was proposed to compute the vertex separator of a tree. However, their algorithm takes O(n log n) time to construct an optimal layout for a tree. It left an open problem whether there exists a linear-time algorithm to construct an optimal layout. Subsequently, Peng et al. used the extended avenue concept to design a linear-time algorithm to construct an optimal search strategy for a tree. Independently, Skodinis proposed another liner-time algorithm to construct an optimal layout for a tree using a different approach from Peng's. In this dissertation, we generalize Parsons' Lemma to general graphs for the node-searching problem. Based on the recursive characterization, we apply the concept of avenue to the node-searching problem on block graphs. Using the concept of avenue and the greedy search strategy, we design a polynomial-time algorithm to compute the search number of a block graph G and to construct an optimal search strategy for G, which answers the open problem that the node-searching problem on block graphs is polynomial-time solvable. Besides, we study the node-searching problem on unicyclic graphs, which have treewidth 2. Bodlaender et al. gave a polynomial-time algorithm for the pathwidth problem, another problem equivalent to the node-searching problem, on partial k-trees for a fixed k >= 1. Their algorithm certainly can be used to solve the problem on unicyclic graphs. However, the time complexity of the algorithm is quite large, Omega(n^{4k+3}). Thus, it takes Omega(n^{11}) time for a graph with treewidth even 2. Recently, Ellis et al. proposed a O(n log n)-time complicated algorithm for the vertex separation problem on unicyclic graphs. In this dissertation, using the concept of oriented search strategy, we propose a linear-time and more simplified algorithm for the node-searching problem on unicyclic graphs.