Detecting a Stationary Target on an Undirected Network

Abstract

Search processes are widely used in the field of Computer Science. Many well defined algorithms also have been established to perform search in various areas of computer science. The motive behind all the search process is to perform search in efficient manner, either time efficient or space efficient. These well-defined algorithms do not always lead in a polynomial solution for an arbitrary problem. Sometimes there are NP-hard problems which are very tough to solve using standard algorithms. In this project, an attempt is made to search a uniformly distributed and single immobile entity on an undirected network. The objective here is to search for the entity in a minimum expected search time with no limit on the length of the search. An immobile entity can be defined as one which cannot move. Its position is stationary throughout the search process. The network is represented by a graph. A methodology is proposed to carry out the search process in minimum possible time resulting in optimal solution.