On the length of the shortest path in a sparse Barak–Erdős graph Full article
| Journal |
Statistics and Probability Letters
ISSN: 0167-7152 |
||||||||
|---|---|---|---|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 190, Article number : 109634, Pages count : DOI: 10.1016/j.spl.2022.109634 | ||||||||
| Tags | Chain length; Chen–Stein method; Directed Erdos–Renyi graph; Food chain; Parallel processing; Random directed graph | ||||||||
| Authors |
|
||||||||
| Affiliations |
|
Funding (1)
| 1 | Russian Foundation for Basic Research | 19-51-15001 |
Abstract:
We consider an inhomogeneous version of the Barak–Erdős graph, i.e. a directed Erdős–Rényi random graph on {1,…,n} with no loop. Given f a Riemann-integrable non-negative function on [0,1]2 and γ>0, we define G(n,f,γ) as the random graph with vertex set {1,…,n} such that for each i<j the directed edge (i,j) is present with probability pi,j(n)=[Formula presented], independently of any other edge. We denote by Ln the length of the shortest path between vertices 1 and n, and take interest in the asymptotic behaviour of Ln as n→∞.
Cite:
Mallein B.
, Tesemnikov P.
On the length of the shortest path in a sparse Barak–Erdős graph
Statistics and Probability Letters. 2022. V.190. 109634 . DOI: 10.1016/j.spl.2022.109634 WOS Scopus РИНЦ OpenAlex
On the length of the shortest path in a sparse Barak–Erdős graph
Statistics and Probability Letters. 2022. V.190. 109634 . DOI: 10.1016/j.spl.2022.109634 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Feb 1, 2022 |
| Accepted: | Jul 19, 2022 |
| Published online: | Jul 25, 2022 |
| Published print: | Nov 8, 2022 |
Identifiers:
| Web of science: | WOS:000838140600005 |
| Scopus: | 2-s2.0-85136268589 |
| Elibrary: | 56213683 |
| OpenAlex: | W4287448525 |