Searching the Nodes of a Graph: Theory and Algorithms

Details Searching the Nodes of a Graph: Theory and Algorithms Searching the Nodes of a Graph: Theory and Algorithms

2009-05-20

arxiv.org/abs/0905.3359v1

Computer Science

Discrete Mathematics

Scientific paper

One or more searchers must capture an invisible evader hiding in the nodes of a graph. We study this graph search problem; we emphasize that we study the capture of a node-located evader, which has received less attention than edge search. We show that in general graphs the problem of node search is easier than that of edge search (however node search is NP-complete, just like edge search). We concentrate on the internal monotone connected (IMC) node search of trees and show that it is essentially equivalent to IMC edge search. For IMC node search on general graphs we present a new algorithm: GSST (Guaranteed Search by Spanning Tree) which clears the graph G by performing all its clearing moves along a spanning tree T of G. We prove the existence of probabilistically complete variants of GSST. Our experiments also indicate that GSST can efficiently node-clear large graphs given only a small running time. An implementation of GSST is also provided and made publicly available.

Affiliated with

Also associated with

No associations

Rating

Searching the Nodes of a Graph: Theory and Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Searching the Nodes of a Graph: Theory and Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching the Nodes of a Graph: Theory and Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-243461