Graph Searching Problem
Participants,
Overview,
Selected results.
Participants
- IIS members:
- Outside members:
-
Chin-Wen Ho, Department of Computer Science and Information
Engineering, National Central University.
- Sheng-Lung Peng, Department of Computer Science and Information
Engineering, National Don Hwa University.
-
Chuan-Yi Tang, Department of Computer Science,
National Tsing Hua University.
Overview
The graph searching problem is a graph-theoretical 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
-
Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and Chuan-Yi Tang,
``Graph Searching on Some Subclasses of Chordal Graphs,''
Algorithmica, volume 27, pages 395--426, 2000.
Extended abstract in
Proc. 7th International Symposium on Algorithms and
Computation (ISAAC), Springer-Verlag
LNCS #1178, pages 156--165, 1996,
under the title ``Graph Searching on Chordal Graphs.''
-
In this paper,
we use a uniform high-level approach to solve the edge and node
searching problems on several special subclasses of chordal graphs.
As a result, we have derived polynomial-time algorithms
on split graphs, interval graphs and $k$-starlike graphs.
-
Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and
Chuan-Yi Tang,
"Edge and Node Searching Problems on Trees,"
Theoretical Computer Science, volume 240, number 2,
pages 429--446, 2000.
Extended abstract in
Proc. 3rd International Computing and Combinatorics Conf.
(COCOON),
Springer-Verlag LNCS #1276, pages 284--293, 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 linear-time 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.
-
Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Chuan-Yi Tang,
"A Linear-time Algorithm for Constructing an Optimal
Node-Search Strategy of a Tree,"
Proc. 4th International Computing and Combinatorics Conf.
(COCOON), Springer-Verlag
LNCS# 1449, pages 279--288, 1998.
-
In this paper, we present a linear-time 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 Tsan-sheng Hsu, last updated April 17, 2001.