Graph Searching Problem
Participants,
Overview,
Selected results.
Participants
 IIS members:
 Outside members:

ChinWen Ho, Department of Computer Science and Information
Engineering, National Central University.
 ShengLung Peng, Department of Computer Science and Information
Engineering, National Don Hwa University.

ChuanYi Tang, Department of Computer Science,
National Tsing Hua University.
Overview
The graph searching problem is a graphtheoretical game played on
an undirected graph considered as a system of tunnels in which all the
tunnels are initially contaminated by a gas.
There are three kinds of moves
in edge searching: (1) placing a searcher on a vertex; (2) removing a
searcher from a vertex; and (3) clear an edge by
either (3.1) moving a searcher from one vertex to another
along an edge or (3.2) placing two searchers on the two endpoints of the edge.
A cleared edge may be recontaminated once
there is a path without any searchers connecting the edge
with a contaminated one.
The goal of this game is to discover
a sequence of moves, called strategy , clear the graph
with the least number of searchers.
The graph searching problem is not only interesting
theoretically, but also have applications on combinatorial problems
including the interval thickness, the pathwidth and the vertex
separation number of a graph.
There are three versions of this problem depending on the
actions allowed to be used in (3).
Searching allowing only (3.1) is called edge searching , while
allowing only (3.2) is called node searching .
In the past, many isolated, but active researches has been performed
on different versions of searching on different classes of graphs.
The results in edge searching normally cannot be used in node
searching, and vice versa.
We have devised a uniform approach in solving
the two versions of the graph searching problem.
Selected results

ShengLung Peng, MingTat Ko, ChinWen Ho, Tsansheng Hsu, and ChuanYi Tang,
``Graph Searching on Some Subclasses of Chordal Graphs,''
Algorithmica, volume 27, pages 395426, 2000.
Extended abstract in
Proc. 7th International Symposium on Algorithms and
Computation (ISAAC), SpringerVerlag
LNCS #1178, pages 156165, 1996,
under the title ``Graph Searching on Chordal Graphs.''

In this paper,
we use a uniform highlevel approach to solve the edge and node
searching problems on several special subclasses of chordal graphs.
As a result, we have derived polynomialtime algorithms
on split graphs, interval graphs and $k$starlike graphs.

ShengLung Peng, ChinWen Ho, Tsansheng Hsu, MingTat Ko, and
ChuanYi Tang,
"Edge and Node Searching Problems on Trees,"
Theoretical Computer Science, volume 240, number 2,
pages 429446, 2000.
Extended abstract in
Proc. 3rd International Computing and Combinatorics Conf.
(COCOON),
SpringerVerlag LNCS #1276, pages 284293, 1997.

Though the above two searching problems appear to be similar,
different techniques have been devised to solve these two problems.
In this paper, we present a lineartime transformation
to relate these two version of searching together when the input
graph is a tree.
We prove that if an optimal node searching strategy is known, then
an optimal edge searching can be obtained in linear time.

ShengLung Peng, ChinWen Ho, Tsansheng Hsu, MingTat Ko, and ChuanYi Tang,
"A Lineartime Algorithm for Constructing an Optimal
NodeSearch Strategy of a Tree,"
Proc. 4th International Computing and Combinatorics Conf.
(COCOON), SpringerVerlag
LNCS# 1449, pages 279288, 1998.

In this paper, we present a lineartime algorithm to
solve the node searching problem on trees.
Thus combining our previous result, we have also solved
the edge searching problem on trees.
Created by Tsansheng Hsu, last updated April 17, 2001.