×

Constrained minimum passage time in random geometric graphs. (English) Zbl 1462.05326

The paper under review considers a random geometric graph where \(n\) points are independently placed in the unit square \([-1/2,1/2]^{n}\) from some density satisfying mild conditions (for example, uniform distribution is covered) and we say two such are adjacent if and only if their distance is at most \(r_{n}\). We assign to each edge a ‘passage time’, modelled as independent identically distributed random variables with a given cumulative distribution function \(F\). A source is then inserted at \(s_{A}=(0,0)\) and a sink at some point \(s_{B}=(d_{n},0)\) and each of these is joined to all vertices within distance \(r_{n}\) of it. The main topic of interest is the minimum passage time of paths from the source to the sink.
Attention focuses on paths which do not wind too much: formally, given \(K\geq 1\), a path from \(s_{A}\) to \(s_{B}\) is said to have stretch at most \(K\) if the number of edges in it (which must trivially be at least \(d_{n}/r_{n}\)) is at most \(Kd_{n}/r_{n}\). The main result gives both upper and lower bounds on the passage time from \(s_{A}\) to \(s_{B}\) of paths of stretch at most \(K\) under various technical assumptions.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C12 Distance in graphs
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Spencer, J., The Probabilistic Method (2008), New Jersy: Wiley Interscience, New Jersy · Zbl 1148.05001 · doi:10.1002/9780470277331
[2] Bradonjic, M.; Elsasser, R.; Friedrich, T.; Sauerwald, T.; Stauffer, A., Efficient Broadcast on Random Geometric Graphs, Proc. SODA, 2010, 1412-1421 (2010) · Zbl 1288.05246
[3] Ferrero, R.; Gandino, F., Analysis of random geometric graph for wireless network configuration, Proc. ICMU, 2017, 1-6 (2017)
[4] Franceschetti, M.; Dousse, O.; Tse, DNC; Thiran, P., Closing Gap in the Capacity of Wireless Networks via Percolation Theory, IEEE Trans. Inf. Theory, 53, 1009-1018 (2007) · Zbl 1310.94004 · doi:10.1109/TIT.2006.890791
[5] Galambos, J., Asymptotic Theory of Extreme Order Statistics (1978), New Jersy: Wiley, New Jersy · Zbl 0381.62039
[6] Gandham, SR; Dawande, M.; Prakash, R.; Venkatesan, S., Energy efficient schemes for wireless sensor networks with multiple mobile base stations, Proc. GLOBECOM, 2003, 377-381 (2003)
[7] Ganesan, G., Infection spread in random geometric graphs, Adv. Appl. Probab., 47, 164-181 (2015) · Zbl 1337.60242 · doi:10.1239/aap/1427814586
[8] Ganesan, G., Stretch and diameter in random geometric graphs, Algorithmica, 80, 300-330 (2018) · Zbl 1380.05179 · doi:10.1007/s00453-016-0253-5
[9] Gupta, P., Kumar, P.R.: Critical Power for Asymptotic Connectivity in Wireless Networks, pp. 2203-2214. Stochastic Analysis, Control, Optimization and Applications (1998)
[10] Meester, R.; Roy, R., Continuum Percolation (1996), Cambridge: Cambridge University Press, Cambridge · Zbl 1146.60076 · doi:10.1017/CBO9780511895357
[11] Muthukrishnan, S.; Pandurangan, G., The bin-covering technique for thresholding random geometric graph properties, Proc. SODA, 2005, 989-998 (2005) · Zbl 1297.05221
[12] Penrose, M., Random Geometric Graphs (2003), Oxford: Oxford University Press, Oxford · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001
[13] Zennaro, D.; Ahmad, A.; Vangelista, L.; Serpedin, E.; Nounou, H.; Nounou, M., Network-wide clock synchronization via message passing with exponentially distributed link delays, IEEE Trans. Commun., 61, 2012-2024 (2013) · doi:10.1109/TCOMM.2013.021913.120595
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.