Navegar

Colección

Datos Estadísticas

Artículo

Bermolen, P.; Jonckheere, M.; Moyal, P. "The jamming constant of uniform random graphs" (2017) Stochastic Processes and their Applications. 127(7):2138-2178
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

By constructing jointly a random graph and an associated exploration process, we define the dynamics of a “parking process” on a class of uniform random graphs as a measure-valued Markov process, representing the empirical degree distribution of non-explored nodes. We then establish a functional law of large numbers for this process as the number of vertices grows to infinity, allowing us to assess the jamming constant of the considered random graphs, i.e. the size of the maximal independent set discovered by the exploration algorithm. This technique, which can be applied to any uniform random graph with a given–possibly unbounded–degree distribution, can be seen as a generalization in the space of measures, of the differential equation method introduced by Wormald. © 2016 Elsevier B.V.

Registro:

Documento: Artículo
Título:The jamming constant of uniform random graphs
Autor:Bermolen, P.; Jonckheere, M.; Moyal, P.
Filiación:Facultad de Ingeniería, Universidad de La Republica, Julio Herrera y Reissig 565, Montevideo, Uruguay
CONICET, Mathematics Department, Facultad de Ciencas Exactas y Naturales, Universidad de Buenos Aires, 1482 Pabellon I, Ciudad Universitaria Buenos Aires, Argentina
Laboratoire de Mathematiques Appliquees LMAC, Universite de Technologie de Compiegne, Rue du Dr Schweitzer CS 60319, Compiegne, 60203, France
IEMS Department, Mc Cormick School of Engineering - Northwestern University, 2145 Sheridan Road, Evanston, IL 60208, United States
Palabras clave:Configuration model; Hydrodynamic limit; Measure-valued Markov process; Parking process; Random graph; Differential equations; Jamming; Markov processes; Configuration model; Degree distributions; Differential equation method; Exploration algorithms; Hydrodynamic limit; Maximal independent set; Primary; Random graphs; Graph theory
Año:2017
Volumen:127
Número:7
Página de inicio:2138
Página de fin:2178
DOI: http://dx.doi.org/10.1016/j.spa.2016.10.005
Título revista:Stochastic Processes and their Applications
Título revista abreviado:Stoch. Processes Appl.
ISSN:03044149
CODEN:STOPB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03044149_v127_n7_p2138_Bermolen

Referencias:

  • Aldous, D.J., Stopping times and tightness (1978) Ann. Probab., 6, pp. 335-340
  • Baccelli, F., Błaszczyszyn, B., (2009) Stochastic Geometry and Wireless Networks, Foundations and Trends in Networking
  • Billingsley, P., Convergence of Probability Measures (1968), John Wiley & Sons; Dawson, D.A., Measure-valued markov processes (1993) Lecture Notes in Mathematics - École d’Été de Probabilités de Saint-Flour XXI, Vol. 1541, pp. 1-260. , Springer Verlag
  • Decreusefond, L., Dhersin, J.S., Moyal, P., Tran, V.C., Large graph limit for an sir process in random network with heterogeneous connectivity (2012) Ann. Appl. Probab., 22 (2), pp. 541-575
  • Decreusefond, L., Moyal, P., A functional central limit theorem for the m/gi/? queue (2008) Ann. Appl. Probab., 18 (6), pp. 2156-2178. , 12
  • Decreusefond, L., Moyal, P., Stochastic Modeling and Analysis of Telecom Networks (2012), ISTE Hoboken, NJ, London; Dynkin, E.B., Markov Processes, Vol. 1 & Vol. 2 (1965); Ethier, S.N., Kurtz, T.G., (1986) Markov Processes: Characterization and Convergence, Wiley Series in Probability and Mathematical Statistics, , J. Wiley & Sons New York, Chichester
  • Evans, J.W., Random and cooperative sequential adsorption (1993) Rev. Modern Phys., 65 (4), p. 1281
  • Ferrari, P., Fernández, R., Garcia, N., Perfect simulation for interacting point processes, loss networks and Ising models (2002) Stochastic Process. Appl., 102 (1), pp. 63-88
  • Finch, S., Mathematical Constants. Encyclopedia of Mathematics and its Applications (Book 94) (2003); Gamarnik, D., Goldberg, D., Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections (2010) Combin. Probab. Comput., 19 (1), pp. 61-85
  • Janson, S., The probability that a random multigraph is simple, ii (2014) J. Appl. Probab., 51A, pp. 123-137. , 12
  • Joffe, A., Métivier, M., Weak convergence of sequences of semimartingales with applications to multitype branching processes (1986) Adv. Appl. Probab., 18, pp. 20-65
  • Kallenberg, O., Random Measures (1983), Academic Press; Kleinrock, L., Tobagi, F.A., Packet switching in radio channels: Part i–carrier sense multiple-access modes and their throughput-delay characteristics (1975) IEEE Trans. Commun., 23 (12), pp. 1400-1416
  • Knuth, D.E., Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, Vol. 10 (1997), American Mathematical Soc; Larroca, F., Bermolen, P., Jonckheere, M., Moyal, P., Estimating the spatial reuse with configuration models (2016) ACM Transactions on Modeling and Performance Evaluation of Computing Systems
  • Luczak, M., Brightwell, G., Janson, S., (2015), https://arxiv.org/abs/1510.05560, The greedy independent set in a random graph with given degrees; McDiarmid, C., Colouring random graphs (1984) Ann. Oper. Res., 1 (3), pp. 183-200
  • Penrose, M.P., Random parking, sequential adsorption, and the jamming limit (2001) Comm. Math. Phys., 218 (1), pp. 153-176
  • Ritchie, T., Construction of the thermodynamic jamming limit for the parking process and other exclusion schemes on Zd (2006) J. Stat. Phys., 122 (3), pp. 381-398
  • Roelly-Coppoletta, S., A criterion of convergence of measure-valued processes: application to measure branching processes (1986) Stochastics, 17 (1-2), pp. 43-65
  • Solomon, H., Random packing density (2003) Proc. Fifth Berkeley Symp. Math. Stat. Probab., pp. 119-134. , L.M. Le Cam J. Neyman Univ. of Calif. Press MR 41(3–4)
  • Tien Viet, N., Baccelli, F., Generating functionals of random packing point processes: From hard-core to carrier sensing (2012), CoRR, abs/1202.0225; van der Hofstad, R., (2013) Random Graphs and Complex Networks, Lecture Notes
  • Wang, J.-S., Series expansion and computer simulation studies of random sequential adsorption (2000) Colloids Surf. A: Physicochem. Eng. Aspects, 165 (1-3), pp. 325-343
  • Wormald, N.C., Differential equations for random processes and random graphs (1995) Ann. Appl. Probab., pp. 1217-1235
  • Wormald, N.C., Models of random regular graphs (1999) London Mathematical Society Lecture Note Series, pp. 239-298
  • Wormald, N.C., Analysis of greedy algorithms on graphs with bounded degrees (2003) Discrete Math., 273 (1), pp. 235-260

Citas:

---------- APA ----------
Bermolen, P., Jonckheere, M. & Moyal, P. (2017) . The jamming constant of uniform random graphs. Stochastic Processes and their Applications, 127(7), 2138-2178.
http://dx.doi.org/10.1016/j.spa.2016.10.005
---------- CHICAGO ----------
Bermolen, P., Jonckheere, M., Moyal, P. "The jamming constant of uniform random graphs" . Stochastic Processes and their Applications 127, no. 7 (2017) : 2138-2178.
http://dx.doi.org/10.1016/j.spa.2016.10.005
---------- MLA ----------
Bermolen, P., Jonckheere, M., Moyal, P. "The jamming constant of uniform random graphs" . Stochastic Processes and their Applications, vol. 127, no. 7, 2017, pp. 2138-2178.
http://dx.doi.org/10.1016/j.spa.2016.10.005
---------- VANCOUVER ----------
Bermolen, P., Jonckheere, M., Moyal, P. The jamming constant of uniform random graphs. Stoch. Processes Appl. 2017;127(7):2138-2178.
http://dx.doi.org/10.1016/j.spa.2016.10.005