Abstract
In the graph searching problem, initially a graph with all its edgescontaminated is presented.The objective is to obtain a state of the graph inwhich all the edges are simultaneously cleared by using the leastnumber of searchers.This number is called the search number of the graph.A search strategy is a sequence of allowable moves that clears theinitial contaminated graph.A search strategy is optimal if the number of searchers used isequal to the search number of the graph.Three variations of the graph searching problem are considered.They are node searching, edge searching and mixed searching.In node searching, an edge is cleared by concurrently having searcherson both of its endpoints.In edge searching, an edge is cleared by moving a searcheralong this edge.In mixed searching, an edge can be cleared either by node searchingrules or by edge searching rules.For these problems on several special classes of graphs,we provide efficient algorithmsThe class of trees is one of the studied special classes of graphs.For the node searching problem, Scheffler presented a fairlycomplicate linear-time algorithm to compute the node-search number ofa tree $T$ and claimed that a linear-time algorithm for constructingan optimal node-search strategy of $T$ easily followed.Unfortunately, few details of her construction are recorded in theliterature.Using an approach different from Scheffler's, Ellis {\it et al}.proposed algorithms to compute the node-search number of an $n$-vertextree $T$ in $O(n)$ time and to construct an optimal node-search strategyof $T$ in $O(n\log n)$ time.An open problem was proposed whether there exists a linear-timealgorithm to construct an optimal node-search strategy of $T$.For the edge searching problem, Megiddo {\it et al}. proposed alinear-time algorithm to compute the edge-search number of $T$.However, their algorithm runs in $O(n\log n)$ time forconstructing an optimal edge-search strategy of $T$.A similar result for the mixed searching problem on trees is shownby Takahashi {\it et al}.They also proposed an $O(n)$-time algorithm to compute themixed-search number of $T$ and an $O(n\log n)$-time algorithmto construct an optimal mixed-search strategy of $T$.An open problem was also proposed whether there exists a linear-timealgorithm to construct an optimal edge-search (and mixed-search)strategy of $T$.In this dissertation, we extend the concept of avenue on a treein edge searching, proposed by Megiddo {\it et al}., to extendedavenue for these three searching problems.Moreover, we propose the concept of extended avenue system of a treefor these three searching problems.An extended avenue system can be transformed to an optimalsearch strategy and this transformation can be done in lineartime if the extended avenue system is implemented by a treestructure, called avenue tree.In node searching and mixed searching, we design a linear-timealgorithm to construct an avenue tree for a tree and anoptimal node-search (mixed-search) strategy is thus obtainedin linear time.Furthermore, we show that there is a relationship between node searchingand edge searching by considering their extended avenue systems respectively.In fact, we show that an extended avenue system in node searchingis also an extended avenue system in edge searching and {\it vice versa} forany sprout tree in which there are at least four vertices with nodegree-2 vertex and every internal vertex is adjacent to at least one leaf.For any tree $T$ which is not a path can be transformed into a sprouttree $T^{\prime}$.We show that the edge-search number of $T$ is equal to the edge-search numberof $T^{\prime}$.Hence, by the relationship we mentioned above, an optimal edge-search strategyof $T$ can be obtained from an optimal node-search strategy of $T^{\prime}$.That is, an optimal edge-search strategy of $T$ can be obtained inlinear time.The class of starlike graphs is another special class of graphs wehave studied on the graph searching problem.Gustedt show that every starlike graph has a normalized optimal node-searchstrategy in which the maximal cliques are cleared one by one.By using a dynamic programming approach, he gave an $O(n^{2k+1})$-time and-space algorithm for the node searching problem on $k$-starlikegraphs for a fixed $k \geq 1$, where $n$ is the number of vertices inthe input graph.For the same problem, we derive necessary and sufficientconditions for a $k$-starlike graph to have a given node-search number.By checking these conditions, it leads to an $O(mn^{k})$-timeand $O(m)$-space algorithm on $k$-starlike graphs for a fixed $k \geq 1$,where $m$ is the number of edges in the input graph.For edge searching and mixed searching, we also derive similar butmore complicated necessary and sufficient conditions respectively.It leads to an $O(mn^{2})$-time and $O(m)$-space algorithm on split graphsand an $O(mn^{k})$-time and $O(m)$-space algorithm on $k$-starlike graphsfor a fixed $k \geq 2$ for the edge and mixed searching problems.There is no polynomial algorithm knownpreviously for the edge and mixed searching problems.In addition, we also show that theedge and mixed searching problems remain NP-complete on chordal graphs.As a by-product, we propose linear time algorithms on interval graphs forthe edge and mixed searching problems.