Exact and Approximation Algorithms for the Expanding Search Problem

Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices s...