Longest path distance in random circuits

Details Longest path distance in random circuits Longest path distance in random circuits

2011-01-28

arxiv.org/abs/1101.5547v1

Mathematics

Probability

20 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Longest path distance in random circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Longest path distance in random circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest path distance in random circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552425