COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Depth-First Search in a Random DigraphAdd 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. |
## Other listsWomen in Academia: Skills and Practices Geometry, Integrability and Twistor Theory Land Economy Seminars Lent 2020## Other talksGlobal High Resolution Modelling of Ocean and Climate Historical backdrop, leading to the alpha-effect --- its origins and limitations (Keynote speaker) Using preconditioning to speed up computations for travelling waves under ice in 3D Sources of uncertainty in simulations of Arctic sea ice and implications for model development needs Gateway Soft Matter |