Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.3, pp.421-430 (September 1993)
An Optimal Algorithm for Edge Searching an Interval Graph

Ruay Shiung Chang
Department of Information Management
National Taiwan Institute of Technology
Taipei, Taiwan, Republic of China

Consider the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edge of a graph, G, in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number, s(G), of searchers that will suffice to guarantee capture of the fugitive? This is called the edge searching problem. This problem is slightly different from the node searching problem, where the clearing of an edge takes place once both its endpoints simultaneously carry a searcher. Both searching problems have been proved to be NP-hard and it has been shown that the node searcher number of an interval graph is equivalent to the size of its maximum clique. In this paper, we present an optimal algorithm to edge-search an interval graph. Conditions are also shown when the edge search number and the node search number are equal and when they differ by 1 for interval graphs.

Keywords: graph theory, interval graph, edge search number, node search number, algorithms

Received September 20, 1992; revised April 13, 1993.
Communicated by Richard C. T. Lee.