Longest path distance in random circuits

DOI10.1017/S0963548312000260MaRDI QIDQ3168445zbMATH OpenWikidataFDO

Authors Nicolas Broutin, Omar Fawzi

Publication date 31 October 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.5547

zbMATH Keywords

dagsnatural distances in random dagsrandom directed acyclic graphs

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Analytic circuit theory (94C05) Miscellaneous topics in information and communication theory (94D99)

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.

Recommendations

• Long and short paths in uniform random recursive dags
• On the shape of a random acyclic digraph
• Bounding variance and expectation of longest path lengths in dags
• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
• On the Expected Depth of Random Circuits

Cites work

• A limit law for outputs in random recursive circuits
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees. II
• Asymptotical growth of a class of random trees
• Depth properties of scaled attachment random recursive trees
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees
• Limit theorems for the minimal position in a branching random walk with independent logconcave displacements
• Long and short paths in uniform random recursive dags
• Maximal displacement of branching brownian motion
• Minima in branching random walks
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• Minimal positions in a branching random walk
• On the Expected Depth of Random Circuits
• Postulates for subadditive processes
• Probability and random processes.
• Stopped Random Walks
• The first birth problem for an age-dependent branching process
• The first- and last-birth problems for a multitype age-dependent branching process
• The height of a random binary search tree
• The power of choice in growing trees
• The power of choice in the construction of recursive trees
• The random multisection problem, travelling waves and the distribution of the height of m-ary search trees
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• Tightness for a family of recursion equations

Cited in

(7)

• Long and short paths in uniform random recursive dags
• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
• On the Expected Depth of Random Circuits
• Bounding variance and expectation of longest path lengths in dags
• The number of descendants in a random directed acyclic graph
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Approximation of subgraph counts in the uniform attachment model

This page was built for publication: Longest path distance in random circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168445)