The Node-Searching Problem on Block Graphs and Unicyclic Graphs
Date Issued
2004
Date
2004
Author(s)
Chou, Hsin-Hung
DOI
en-US
Abstract
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.
Subjects
區塊圖
點搜尋問題
通道觀念
最佳搜尋策略
搜尋數
單環圖
貪婪搜尋策略
導向搜尋策略
search number
avenue concept
oriented search strategy
block graphs
node-searching problem
optimal search strategy
unicyclic graphs
greedy search strategy
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-D86526005-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):9249a734640a8c76774e5b838c5edca1