Depth-First Search in a Random Digraph

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

• Svante Janson (Uppsala Universitet)
• Tuesday 06 September 2022, 16:30-17:30
• MR9, Centre for Mathematical Sciences.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR9, Centre for Mathematical Sciences
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.