Average costs of a graph exploration: Upper and lower bounds

摘要

We consider the exploration of random digraphs. We give upper and lower bounds for the expected number of edges traversed during an exploration. This result implies a lower bound for the expected running time of a wide class of algorithms, e.g., breadth-first-search, depth-first-search, and algorithms to determine a minimum spanning tree or to solve the single sourer shortest paths problem in a weighted digraph. Furthermore, we investigate the connectedness of nonhomogeneous random digraphs and we point out the relationship with the exploration algorithms. (C) 2000 Academic Press. [References: 15]