University of Cambridge > > Probability > Depth-First Search in a Random Digraph

Depth-First Search in a Random Digraph

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Jason Miller.

We study the Depth-First Search algorithm, applied to a random digraph ($=$ directed graph). The random digraph is constructed by giving the vertices i.i.d.\ outdegrees, and choosing the endpoint of all arcs independently and uniformly at random. (Loops and multiple edges are allowed, but not important.) The Depth-First Search can be regarded as building a forest which eventually contains all vertices. One important property is the depth of vertices in this forest, i.e.\ the distance to the root. A particularly simple case is when the outdegree distribution is geometric. Its lack of memory implies that that the depths of the evrtices form a Markov process, which can be analyzed. For a general outdegree distribution, this is no longer true; as a substitute, we study a related process, which is Markov, and then are able to draw conclusions also for the depth. (Based on joint work with Philippe Jacquet.)

This talk is part of the Probability series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity