Longest Path Distance in Random Circuits

DOI10.1017/S0963548312000260zbMath1252.05049arXiv1101.5547WikidataQ62556723 ScholiaQ62556723MaRDI QIDQ3168445

Omar Fawzi, Nicolas Broutin

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) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Combinatorial probability (60C05) Analytic circuit theory (94C05) Distance in graphs (05C12) Miscellaneous topics in information and communication theory (94D99)

Related Items

The number of descendants in a random directed acyclic graph

Cites Work

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

This page was built for publication: Longest Path Distance in Random Circuits