Longest path distance in random circuits

Abstract : We study distance properties of a general class of random directed acyclic graphs (DAGs). In a DAG, many natural notions of distance are possible, for there exists multiple paths between pairs of nodes. The distance of interest for circuits is the maximum length of a path between two nodes. We give laws of large numbers for the typical depth (distance to the root) and the minimum depth in a random DAG. This completes the study of natural distances in random DAGs initiated (in the uniform case) by Devroye and Janson (2009+). We also obtain large deviation bounds for the minimum of a branching random walk with constant branching, which can be seen as a simplified version of our main result.
Type de document :
Article dans une revue
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2012, 21 (6), pp.856-881. 〈10.1017/S0963548312000260〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00773368
Contributeur : Nicolas Broutin <>
Soumis le : dimanche 13 janvier 2013 - 16:08:03
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

Collections

Citation

Nicolas Broutin, Omar Fawzi. Longest path distance in random circuits. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2012, 21 (6), pp.856-881. 〈10.1017/S0963548312000260〉. 〈hal-00773368〉

Partager

Métriques

Consultations de la notice

153