Combinatorics, Probability and Computing

Paper

Longest Path Distance in Random Circuits

NICOLAS BROUTINa1 and OMAR FAWZIa2

a1 INRIA Rocquencourt, 78153 Le Chesnay, France (e-mail: nicolas.broutin@inria.fr)

a2 School of Computer Science, McGill University, H3A 2K6, Montreal, Canada (e-mail: ofawzi@cs.mcgill.ca)

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 exist 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. 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.

(Received January 27 2011)

(Revised May 27 2012)

(Online publication July 03 2012)

AMS 2010 Mathematics subject classification:

  • Primary 60C05;
  • 05C05;
  • 94D99