Ricerc@Sapienza

We study a number of graph exploration problems in the following natural scenario: an algorithm starts exploring an undirected graph from some seed vertex; the algorithm, for an arbitrary vertex v that it is aware of, can ask an oracle to return the set of the neighbors of v.

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process. To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G = (V, E) with a source vertex s, stochastic edge costs drawn from a distribution πe, e ∈ E, and rewards on vertices of maximum value R.