×

zbMATH — the first resource for mathematics

Longest path distance in random circuits. (English) Zbl 1252.05049
Summary: 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 L. Devroye and S. Janson [Ark. Mat. 49, No. 1, 61–77 (2011; Zbl 1230.60092)]. 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.
MSC:
05C12 Distance in graphs
05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
94C05 Analytic circuit theory
60C05 Combinatorial probability
05C05 Trees
94D99 Miscellaneous topics in information and communication theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Algorithms: ESA ’96 pp 208– (1996)
[2] DOI: 10.1002/rsa.20391 · Zbl 1247.05217 · doi:10.1002/rsa.20391
[3] Convex Analysis (1970) · Zbl 0932.90001 · doi:10.1515/9781400873173
[4] DOI: 10.1145/765568.765571 · Zbl 1325.68076 · doi:10.1145/765568.765571
[5] DOI: 10.1214/aop/1176993000 · Zbl 0563.60010 · doi:10.1214/aop/1176993000
[6] DOI: 10.1214/aoap/1177004832 · Zbl 0836.60089 · doi:10.1214/aoap/1177004832
[7] DOI: 10.1007/s00236-004-0152-0 · Zbl 1101.68069 · doi:10.1007/s00236-004-0152-0
[8] DOI: 10.1002/rsa.3240070102 · Zbl 0835.05062 · doi:10.1002/rsa.3240070102
[9] DOI: 10.1007/s11512-009-0118-0 · Zbl 1230.60092 · doi:10.1007/s11512-009-0118-0
[10] Probabilistic Methods for Algorithmic Discrete Mathematics pp 249– (1998) · doi:10.1007/978-3-662-12788-9_7
[11] DOI: 10.1145/5925.5930 · Zbl 0741.05062 · doi:10.1145/5925.5930
[12] Large Deviations Techniques and Applications (1998) · Zbl 0896.60013 · doi:10.1007/978-1-4612-5320-4
[13] DOI: 10.1214/08-AOP414 · Zbl 1169.60020 · doi:10.1214/08-AOP414
[14] DOI: 10.1002/cpa.3160310502 · Zbl 0361.60052 · doi:10.1002/cpa.3160310502
[15] Algorithms: ESA ’95 pp 102– (1995)
[16] DOI: 10.2307/1426138 · Zbl 0339.60074 · doi:10.2307/1426138
[17] DOI: 10.1239/aap/1013540028 · Zbl 0973.60098 · doi:10.1239/aap/1013540028
[18] DOI: 10.1214/aoms/1177729330 · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[19] Branching Processes (1972) · Zbl 0259.60002 · doi:10.1007/978-3-642-65371-1
[20] DOI: 10.1007/s00453-006-0107-7 · Zbl 1117.68095 · doi:10.1007/s00453-006-0107-7
[21] DOI: 10.1017/S096354839900382X · Zbl 0941.68001 · doi:10.1017/S096354839900382X
[22] The Probabilistic Method (2008)
[23] DOI: 10.1214/08-AOP428 · Zbl 1196.60142 · doi:10.1214/08-AOP428
[24] DOI: 10.1007/s11009-009-9159-x · Zbl 1209.05227 · doi:10.1007/s11009-009-9159-x
[25] DOI: 10.1214/aop/1176996266 · Zbl 0325.60079 · doi:10.1214/aop/1176996266
[26] DOI: 10.1214/08-AOP419 · Zbl 1169.60021 · doi:10.1214/08-AOP419
[27] DOI: 10.1214/aop/1176996611 · Zbl 0303.60044 · doi:10.1214/aop/1176996611
[28] Stopped Random Walks: Limit Theorems and Applications (2009) · Zbl 1166.60001
[29] Probability and Random Processes (2001) · Zbl 1015.60002
[30] DOI: 10.1140/epjb/e2007-00310-5 · Zbl 1189.05157 · doi:10.1140/epjb/e2007-00310-5
[31] DOI: 10.1145/765568.765572 · Zbl 1325.68074 · doi:10.1145/765568.765572
[32] DOI: 10.1007/s00453-001-0044-4 · Zbl 0989.68107 · doi:10.1007/s00453-001-0044-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.