On the optimality of discrete strategies for search on graphs (Q5942465)

Searching nets problems by use of the geometrical method are considered. An idea of discrete strategies and corresponding discrete algorithms for searching with use of the finite graphs with an arbitrary topology are introduced. The description of the algorithm from 0-step to K-step is demonstrated by a special example. Two statements showing advantage of the discrete search are presented and a comparison theorem is proved. Additionally it is shown that in application of the approach propoused to concrete graphs one can get the known search strategies, i.e. the left-sided bypass of a tree.